LeetCode 946 验证栈序列[栈 模拟] HERODING的LeetCode之路

解题思路：
既然是验证栈的序列，不如直接定义一个栈进行模拟，模拟是否满足入栈出栈要求，由于值不重复，所以入栈出栈的顺序就唯一，只要找到这个顺序即可，首先不断入栈，当栈尾和popped的index位置相同，弹出，然后不断重复该操作，最后栈空返回true，代码如下：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int n = pushed.size();
        s.push(pushed[0]);
        int index1 = 1, index2 = 0;
        while(!s.empty()) {
            while(!s.empty() && s.top() == popped[index2]) {
                s.pop();
                index2 ++;
            }
            if(index1 >= n || index2 >= n) {
                break;
            }
            s.push(pushed[index1 ++]);
        }
        return s.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20