使用一个 memset 数组和一个堆栈在 O(n) 中找到数组的下一个更大的元素

Question

我的代码不适用于输入：

10 3 *12* 4 2 9 13 0 8 11 1 7 5 6

它的正确输出是：

12 12 *13* 9 9 13 -1 8 11 -1 7 -1 6 -1

而您的代码的输出是：

12 12 *-1* 9 13 13 -1 8 11 -1 7 -1 6 -1

我能看到的是，因为在 while(!s.empty() && a>s.top()) 部分我没有存储 a<s.top() 的那些元素的索引值，我想不出任何方法来这样做。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll a,i,c[n];
        memset(c,-1,sizeof(c));
        stack <int> s;
        for(i=0;i<n;i++){
            cin>>a;
            if(s.empty()){
                s.push(a);
            }
            else{
                if(a>s.top()){
                    int k=i;
                    while(!s.empty() && a>s.top()){
                        s.pop();
                        c[k-1]=a;
                        k--;
                    }
                    s.push(a);
                }
                else{
                    s.push(a);
                    continue;
                }
            }
        }
        for(i=0;i<n;i++)
            cout<<c[i]<<" ";
        cout<<endl;
    }
}

Answer 1

您的代码中有一个小错误。当您更新 c[index]=value 的值时，index 不正确。在处理过程中，您从 stack 中弹出一些元素并将值压入末尾（例如：位置 10 的值可以压入 0 到 10 之间的任何位置），但是在向后退时，您不知道该值的正确位置是什么。

因此，我对您的代码进行了幻灯片更改，跟踪值的位置以及值本身。所以，当我更新 c[index]=value 时，我知道 s.top() 元素的正确索引。

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll a,i,c[n];
        memset(c,-1,sizeof(c));
        stack < pair<int,int> > s;
        for(i=0;i<n;i++){
            cin>>a;
            if(s.empty()){
                s.push({a,i});
            }
            else{
                if(a>s.top().first){
                    while(!s.empty() && a>s.top().first){
                        c[s.top().second]=a;
                        s.pop();
                    }
                    s.push({a,i});
                }
                else{
                    s.push({a,i});
                    continue;
                }
            }
        }
        for(i=0;i<n;i++)
            cout<<c[i]<<" ";
        cout<<endl;
    }
}

输入和输出：

1                                                                                                                               
15                                                                                                                              
14 10 3 12 4 2 9 13 0 8 11 1 7 5 6                                                                                              
-1 12 12 13 9 9 13 -1 8 11 -1 7 -1 6 -1

使用一个 memset 数组和一个堆栈在 O(n) 中找到数组的下一个更大的元素

find next greater element of a array in O(n) using one memset array and a single stack

c++

stack

store

memset

while-loop