使用栈查找下一个更大元素时出现Segmentation Fault问题求助

Hey there, let's break down why your code crashes right when you start debugging—this is a super common pitfall with stack-based array algorithms!

The Root Cause of the Crash #

Your code hits undefined behavior (and thus crashes) because of the order of conditions in your while loop:

while(arr[i]>=s.top() && s.size()>0)

Here, you first check arr[i] >= s.top() before verifying if the stack is empty. When the stack gets emptied during loop iterations, calling s.top() on an empty stack is invalid in C++—this triggers undefined behavior, which almost always leads to an immediate crash.

Fixes to Get Your Code Working #

Let's fix two key issues to get your algorithm running smoothly:

1. Reorder the while loop conditions
   Always check if the stack is non-empty first, so you only access s.top() when it's safe:

   while(!s.empty() && arr[i] >= s.top())
   

   This ensures we never try to read from an empty stack, eliminating the crash trigger.

2. Reverse the result vector
   Since you're traversing the array from right to left, the v vector gets filled with results in reverse order. To match the original array's sequence, you need to reverse v at the end (don't forget to include the <algorithm> header for the reverse function).

Full Fixed Code #

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

using namespace std;

int main() {
    int arr[]{1, 3, 22, 4, 1, -3, 3, 7};
    int n{sizeof(arr)/sizeof(int)};
    vector<int> v;
    stack<int> s;

    for(int i{n-1}; i >= 0; i--) {
        if(s.empty()) {
            v.push_back(-1);
        } else if(arr[i] < s.top()) {
            v.push_back(s.top());
        } else {
            // Check stack non-empty first to avoid invalid top() call
            while(!s.empty() && arr[i] >= s.top()) {
                s.pop();
            }
            v.push_back(s.empty() ? -1 : s.top());
        }
        s.push(arr[i]);
    }

    // Reverse to align results with original array order
    reverse(v.begin(), v.end());

    // Print to verify correctness
    for(int num : v) {
        cout << num << " ";
    }
    // Expected output: 3 22 -1 7 3 3 7 -1
    return 0;
}

Quick Breakdown of the Fixes #

• The condition reordering eliminates the empty stack access that caused the crash.
• Reversing the vector ensures each element in v corresponds to the same index in the original arr (so the first element of v is the next greater element of arr[0], and so on).

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