Medium

题目描述

给定两个整数数组 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. 模拟法（推荐）：使用一个栈来模拟 push 和 pop 操作

    • 遍历 pushed 数组，将元素依次入栈
    • 在每次入栈后，检查栈顶元素是否等于 popped 数组中当前需要弹出的元素
    • 如果相等，就执行弹出操作，并移动 popped 的指针
    • 继续这个过程直到无法再弹出为止

  2. 优化思路：由于题目保证 popped 是 pushed 的排列，我们只需要验证操作顺序是否合法即可

具体实现时，我们维护一个指向 popped 数组的指针，每当栈顶元素与该指针指向的元素相等时，就执行弹出操作。最终如果栈为空，说明序列合法。

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是数组长度。每个元素最多入栈和出栈各一次。

代码实现

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int j = 0;
        
        for (int x : pushed) {
            st.push(x);
            while (!st.empty() && st.top() == popped[j]) {
                st.pop();
                j++;
            }
        }
        
        return st.empty();
    }
};

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        j = 0
        
        for x in pushed:
            stack.append(x)
            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1
        
        return len(stack) == 0

public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        Stack<int> stack = new Stack<int>();
        int j = 0;
        
        foreach (int x in pushed) {
            stack.Push(x);
            while (stack.Count > 0 && stack.Peek() == popped[j]) {
                stack.Pop();
                j++;
            }
        }
        
        return stack.Count == 0;
    }
}

var validateStackSequences = function(pushed, popped) {
    let stack = [];
    let j = 0;
    
    for (let x of pushed) {
        stack.push(x);
        while (stack.length > 0 && stack[stack.length - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多入栈和出栈各一次
空间复杂度O(n)辅助栈的空间开销，最坏情况下存储所有元素