Stack 合集

前言

使用语言 Python, 只针对 LC Medium 和 Hard 题, 面向面试刷题
Note: 除非你面前端 (加上 JS) , 否则统一使用 Python 进行刷题

---

知识点

• Python 用 list 当 stack，后进先出（LIFO）

基本操作

stack = []

# 入栈
stack.append(item)

# 出栈
stack.pop()

# 查看栈顶（不弹出）
stack[-1]

# 判断是否为空
if stack:        # 有元素
if not stack:    # 空
len(stack) == 0  # 空

stack = []

stack.append(1)      # [1]
stack.append(2)      # [1, 2]
stack.append(3)      # [1, 2, 3]

stack[-1]            # 3（栈顶）
stack.pop()          # 3，stack 变成 [1, 2]
stack.pop()          # 2，stack 变成 [1]

单调栈模板

# 单调递增栈（栈底到栈顶递增）
stack = []
for i, num in enumerate(nums):
    while stack and nums[stack[-1]] > num:
        stack.pop()
    stack.append(i)

# 单调递减栈（栈底到栈顶递减）
stack = []
for i, num in enumerate(nums):
    while stack and nums[stack[-1]] < num:
        stack.pop()
    stack.append(i)

---

题目

LC 768

• 768 (Max Chunks To Make Sorted II)

用单调递增栈，栈内的值是每一个 chuck 的最大值

LC 20

• 20 (Valid Parentheses)

LC 739

• 739 (Daily Temperatures)

维护单调递减栈, 栈里存“还没等到更高温度的天”. 一旦遇到更高温度, 就不断弹栈, 并计算等待天数

LC 71

• 71 (Simplify Path)

LC 224

• 224 (Basic Calculator)

属于 Hard 里需要多刷的题, 遇到 ( 就“存档”, 遇到 ) 就“结算并恢复”

elif c == ')':
    result += sign * num   # 先算完括号内部
    num = 0
    result *= stack.pop()  # 乘上括号前的 sign
    result += stack.pop()  # 加回外层 result

LC 394

• 394 (Decode String)

LC 84

• 84 (Largest Rectangle in Histogram)

用单调递增栈, 一旦遇到更小高度，就可以“结算”之前柱子的最大矩形

heights = [2,1,5,6,2,3]

当遇到 2 时，会 pop 6

height = 6
left boundary = index of 5
right boundary = i = 4
width = 4 - 2 - 1 = 1
area = 6 * 1 = 6

然后 pop 5

height = 5
width = 4 - 1 - 1 = 2
area = 5 * 2 = 10   ← 最大

LC 772

• 772 (Basic Calculator III)

这题比 224 复杂, 多刷

LC 227

• 227 (Basic Calculator II)

这题属于 772 的一个子集

LC 316

• 316 (Remove Duplicate Letters)

构造一个单增栈, 遇到更小字符时, 如果之前的字符后面还能再出现, 就把它弹掉

LC 496

• 496 (Next Greater Element I)

LC 1249

• 1249 (Minimum Remove to Make Valid Parentheses)

LC 32

• 32 (Longest Valid Parentheses)

这题 stack 里存的是合法子串的左边界索引 (e.g. 上一个不可能参与有效匹配的位置)

LC 735

• 735 (Asteroid Collision)

这题算是比较有趣的 stack 题, 新行星只会与当前存活序列的尾部发生冲突