剑指 Offer 31 栈的压入、弹出序列

概述

https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

https://leetcode.com/problems/validate-stack-sequences/

暴力法

暴力遍历所有可能的弹出顺序，输入哈希表标记，之后查询给定弹出序列是否存在于哈希表中即可。

模拟法

维护一个栈，遍历弹出序列，则第一个比：

1. 存在于栈顶，
2. 或存在于剩余未遍历的压入序列。

如果不属于这两种情况，说明弹出序列于压入序列组合不合法，返回 false。

否则就继续检查弹出序列中下一个值。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int j = 0;
        for (int i = 0; i < popped.size(); i ++) {
            int target = popped[i];
            if (s.empty() || s.top() != target) {
                while (j < pushed.size() && pushed[j] != target) {
                    s.push(pushed[j]);
                    j ++;
                }
                if (j == pushed.size()) {
                    return false;
                }
                j ++;                
            } else {
                s.pop();
            }
        }
        return true;
    }
};