Next Greater Element算法代码出现段错误的原因排查及修复咨询

我帮你找到了导致段错误的核心原因，咱们一步步拆解来看：
当处理某个元素时，如果它比栈中所有剩余元素都大，while(!stk.empty() && stk.top() <= arr[i])这个循环会把栈里的元素全部弹出，此时栈stk变成空的，但你紧接着执行了resStack.push(stk.top())——空栈调用top()是未定义行为，直接触发了段错误。

修复方案 #

只需要在弹出完栈中小于当前元素的元素后，先判断栈是否为空：

• 如果栈为空，说明当前元素右侧没有更大的元素，往resStack里push -1
• 如果栈不为空，再push栈顶元素

修复后的完整代码 #

#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution {
public:
    //Function to find the next greater element for each element of the array.
    vector<long long> nextLargerElement(vector<long long> arr, int n){
        vector<long long> res;
        stack<long long> stk, resStack;
        for(int i=n-1; i>=0; i--){
            if(stk.empty()){
                resStack.push(-1);
                stk.push(arr[i]);
            }
            else{
                while(!stk.empty() && stk.top() <= arr[i])
                    stk.pop();
                // 关键修改：先判断栈是否为空再操作
                if(stk.empty()){
                    resStack.push(-1);
                }
                else{
                    resStack.push(stk.top());
                }
                stk.push(arr[i]);
            }
        }
        while(!resStack.empty()){
            res.push_back(resStack.top());
            resStack.pop();
        }
        return res;
    }
};
// { Driver Code Starts.
int main() {
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<long long> arr(n);
        for(int i=0;i<n;i++)
            cin>>arr[i];
        Solution obj;
        vector <long long> res = obj.nextLargerElement(arr, n);
        for (long long i : res)
            cout << i << " ";
        cout<<endl;
    }
    return 0;
}
// } Driver Code Ends

额外优化建议 #

其实你可以不用额外的resStack，直接从后往前填充结果数组，这样能节省一点空间，代码也更简洁：

vector<long long> nextLargerElement(vector<long long> arr, int n){
    vector<long long> res(n);
    stack<long long> stk;
    for(int i=n-1; i>=0; i--){
        while(!stk.empty() && stk.top() <= arr[i])
            stk.pop();
        res[i] = stk.empty() ? -1 : stk.top();
        stk.push(arr[i]);
    }
    return res;
}

这个版本直接把结果存在res数组的对应位置，避免了两次栈的中转操作，效率更高。

内容的提问来源于stack exchange，提问作者Manik Badshah