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

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 Offer 31. 栈的压入、弹出序列

问题描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例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 之前弹出。

限制：

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。

解题思路

视频讲解直达：本题视频讲解

代码实现

时间复杂度：O(n)
额外空间复杂度：O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed == null || pushed.length <= 0){
            return true;
        }
        int k = 0;
        Stack<Integer> stack = new Stack();
        for(int i = 0; i < pushed.length; i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[k]){
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();
    }
}

Python

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        if not pushed:
            return True
        k = 0
        stack = []
        for i in range(len(pushed)):
            stack.append(pushed[i])
            while stack and stack[-1] == popped[k]:
                stack.pop()
                k += 1
        return not stack

C++

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

Go

func validateStackSequences(pushed []int, popped []int) bool {
    if len(pushed) == 0 {
        return true
    }
    k := 0
    stack := []int{}
    for _, v := range pushed {
        stack = append(stack, v)
        for len(stack) > 0 && stack[len(stack)-1] == popped[k] {
            stack = stack[:len(stack)-1]
            k++
        }
    }
    return len(stack) == 0
}

JS

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    if (pushed == null || pushed.length <= 0) {
        return true;
    }
    var k = 0;
    var stack = [];
    for (var i = 0; i < pushed.length; i++) {
        stack.push(pushed[i]);
        while (stack.length > 0 && stack[stack.length - 1] == popped[k]) {
            stack.pop();
            k++;
        }
    }
    return stack.length == 0;
};

剑指offer题解