[LeetCode][946]【学习日记】验证栈序列——模拟栈行为

题目

验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出
pop 操作序列的结果时，返回 true；否则，返回 false。

示例 1：

输入： pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true

解释：我们可以按以下顺序执行：

• push(1), push(2), push(3), push(4), pop() -> 4,
• push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入： pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false

解释：1 不能在 2 之前弹出。

提示：

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed 的所有元素互不相同
• popped.length == pushed.length
• popped 是 pushed 的一个排列

思考

• 从题目给的两个序列可知，出栈序列是在入栈过程中经过出栈得到的，所以我们也可以设置一个模拟栈，模拟入栈和出栈的顺序，依次记录每个出栈元素，如果最终得到的出栈序列和题目给的一样，那么题目的出栈序列就是合法的。
• 由于出栈序列是入栈序列的排列，所以如果题目给的出栈序列正确的话，那么按照题目给的入栈顺序和出栈顺序操作后栈将为空

解法：

1. 遍历入栈序列，依次入栈
2. 当入栈元素与出栈元素相等，则弹出，检查栈顶元素和下一个出栈元素是否相等，如果相等，循环执行2
3. 循环结束条件为入栈序列的遍历结束：因为经过观察示例，在入栈完毕后就应该得到最终的出栈序列

• 下面两段代码都是一样思想，不同在于第一段代码在第一次检测到相等元素后没有执行入栈操作，导致了比较多的分支判断
• 代码1

class Solution {
public:
    bool validateStackSequences(vector<int>& putIn, vector<int>& takeOut) {
        stack<int> s;
        int i=0, j=0;
        while(i<putIn.size()){
            if(putIn[i] != takeOut[j]){
                s.push(putIn[i]);
                ++i;
                continue;
            } 
            else{//要入栈的元素和出栈元素相等
                ++i;
                ++j;
                while(!s.empty() && s.top() == takeOut[j]){
                    s.pop();
                    ++j;
                }
                
                continue;
            }
        }

        return s.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 代码2

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int j=0;
        for(auto ele:pushed){
            s.push(ele);
            while(!s.empty() && s.top()==popped[j]){
                s.pop();
                ++j;
            }
        }
        return s.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15