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

Tag: 剑指-Offer Posted on 2022-02-25 20:48:48 Edited on 2022-02-25 21:09:20 Views: 143

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/