946.验证栈序列
#栈 2024-08-15 
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
27
28
29
30
31
32
33
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> data;
        int len = pushed.size();
        int pushLine = 0;
        int popLine = 0;

        for(pushLine; pushLine < len;){
            if(pushed[pushLine] == popped[popLine]){
                popLine++;
                pushLine++;
            }else{
                if(!data.empty() && (popped[popLine] == data.top())){
                    data.pop();
                    popLine++;
                }else{
                    data.push(pushed[pushLine]);
                    pushLine++;
                }
            }
        }

        for(popLine; popLine < len; popLine++){
            if(popped[popLine] != data.top()){
                return false;
            }
            data.pop();
        }

        return true;
    }
};

上面这份代码较为原始，明显感受出是按照正常思维去解题，就让我想起《最小栈》那道题，在简单思考可行性之后就开始写代码，也没想过有些地方可以被优化。优化的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> data;
        int len = pushed.size(); 
        int popLine = 0; 

        for (int pushLine = 0; pushLine < len; ++pushLine) {
            data.push(pushed[pushLine]);

            while (!data.empty() && data.top() == popped[popLine]) {	// 核心优化
                data.pop(); 
                ++popLine;  
            }
        }
        
        return data.empty();
    }
};

其实就相当于把我源代码中的最后一个 for 循环的操作放到第一个 for 循环中用 while 循环处理了。