algorithm - 需要找到数组中每个元素的下一个更大的元素

Question

<分区>

Answer 1

借助两个堆栈(一个用于索引，另一个用于值)，这可以在 O(N) 时间和 O(N) 额外内存空间内完成.

我将借助您的示例解释该算法。

Input  12 15 22  9  7  2 18 23 27 

Initialize Output Array O[] as all -1.

1. Start from the first element. Set CurrentElement = A[0] (12). index = 0   
2. Push A[index] in a Stack S_values. Push index in a Stack S_indices.  
3. Increment index.  
4. while ( S_values is not empty && A[index] is > than S_values.top() )  
   - Set output_index = S_indices.top()
   - set O[output_index] = A[index].  
   - S_values.pop()
   - S_indices.pop().      
5. If index < length(Input)-1 Goto Step 2.
6. Set O[index] = -1. // Last element.

这是可行的，因为堆栈顶部的 S_values 应始终具有最低值，并且元素应按升序从中弹出。类似地，堆栈 S_indices 应始终将最大值放在顶部，索引应按降序弹出。

编辑:C++ 代码

#include <vector>
#include <stack>
#include <iostream>

using std::cout;
using std::endl;
using std::vector;
using std::stack;

int main()
{
    vector<int> Input = { 12, 15, 22,  9,  7,  2, 18, 23, 27};
    vector<int> Output( Input.size(), -1 );

    stack<int> S_values, S_indices;
    S_values.push( Input[0] );
    S_indices.push( 0 );
    for ( size_t index = 1; index < Input.size(); ++index )
    {
        while ( !S_values.empty() && Input[index] > S_values.top() )
        {
            size_t output_index = S_indices.top();
            Output[ output_index ] = Input[ index ];
            S_values.pop();
            S_indices.pop();

        }
        S_values.push( Input[index] );
        S_indices.push( index );
    }

    for ( auto &x : Output )
        cout << x << " ";
    cout << endl;

    return 0;
}

输出:

15 22 23 18 18 18 23 27 -1