使用一个内存集数组和单个堆栈在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