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

Categories:

题目描述
思路分析
1. 解法一：栈模拟（推荐）
相似题目

题目描述

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

思路分析

解法一：栈模拟（推荐）

核心思路：

按 pushed 顺序入栈。

每次入栈后，尽可能弹出与 popped 当前指针相等的元素。

最终若栈为空且 popped 全部匹配，则序列合法。

复杂度分析：

时间复杂度：O(n)，其中 n 表示序列长度。

空间复杂度：O(n)。

// 栈模拟压入与弹出
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0;

        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }

        return stack.isEmpty();
    }
}

// 栈模拟压入与弹出
func validateStackSequences(pushed []int, popped []int) bool {
	stack := make([]int, 0, len(pushed))
	j := 0

	for _, x := range pushed {
		stack = append(stack, x)
		for len(stack) > 0 && j < len(popped) && stack[len(stack)-1] == popped[j] {
			stack = stack[:len(stack)-1]
			j++
		}
	}

	return len(stack) == 0
}

相似题目

题目	难度	考察点
946. 验证栈序列	中等	栈
20. 有效的括号	简单	栈
155. 最小栈	简单	栈
225. 用队列实现栈	简单	栈
232. 用栈实现队列	简单	栈
735. 小行星碰撞	中等	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/44422782