0 Stack Basic

栈是什么？
栈是一种受限的线性表：只允许在同一端（栈顶 top）进行插入和删除。
- LIFO（Last In, First Out）：后进先出
- 两个核心操作：push（入栈）、pop（出栈）
- 辅助操作：peek/top（看栈顶不弹出）、isEmpty、size

	栈 Stack	队列 Queue
顺序	LIFO 后进先出	FIFO 先进先出
操作端	同一端	两端（尾进头出）
典型算法	DFS、回溯、单调栈、表达式求值	BFS、拓扑排序、滑动窗口(单调队列)
Python 实现	`list`	`collections.deque`

实现方式：

数组实现（顺序栈）：

1stack = []
2stack.append(x)      # push, 摊还 O(1)
3x = stack.pop()      # pop,  O(1)
4x = stack[-1]        # peek, O(1)
5if not stack: ...    # isEmpty
6len(stack)           # size

链表实现（链式栈）：头插法建链表，头结点即栈顶

 1class Node:
 2    def __init__(self, val, nxt=None):
 3        self.val, self.next = val, nxt
 4
 5class LinkedStack:
 6    def __init__(self):
 7        self.head = None      # 栈顶
 8        self.n = 0
 9
10    def push(self, val):
11        self.head = Node(val, self.head)   # 新节点指向旧栈顶
12        self.n += 1
13
14    def pop(self):
15        val = self.head.val
16        self.head = self.head.next
17        self.n -= 1
18        return val

操作	数组栈	链表栈
push/pop	摊还 O(1)	严格 O(1)
空间	可能有预留空位	每个元素多一个指针
缓存友好	连续内存	节点分散

1 栈的设计与模拟

1.1 最小栈 | Medium

题目：设计支持 push / pop / top / getMin 的栈，所有操作 O(1)

思路分析：普通栈 pop 后无法回溯历史最小值。解法是 辅助栈（同步栈）：

min_stack[i] 记录「主栈前 i+1 个元素中的最小值」
push 时：min_stack.append(min(val, min_stack[-1]))
pop 时：两栈同步弹出

踩坑记录：

初始栈设置哨兵才能做min比较

代码：

 1class MinStack:
 2
 3    def __init__(self):
 4        self.stack = []
 5        self.min_stack = [math.inf]
 6        
 7    def push(self, value: int) -> None:
 8        self.stack.append(value)
 9        self.min_stack.append(min(value, self.min_stack[-1]))
10
11    def pop(self) -> None:
12        self.stack.pop()
13        self.min_stack.pop()
14
15    def top(self) -> int:
16        return self.stack[-1]
17
18    def getMin(self) -> int:
19        return self.min_stack[-1]

复杂度：

时间：四个操作均 O(1)
空间 O(n)：辅助栈与主栈等长

2 匹配 / 保存现场栈

2.1 有效的括号 | Easy

题目：给定只含 ()[]{} 的字符串，判断是否有效：左右括号类型匹配且顺序正确

思路分析：

括号最终需要完全匹配，字符串长度必须是偶数，可以提前剪枝
用 dict 建立 右括号 → 左括号 的映射
左括号：直接入栈
右括号：
- 栈为空或者栈顶不是与右括号匹配的左括号，匹配失败，如")(", "(]"
- 栈顶是匹配的右括号，匹配成功，pop

踩坑记录：

一定要记得判断栈是不是空not stack
最终一定要判断是不是空栈not stack，如"(("

代码：

 1class Solution:
 2    def isValid(self, s: str) -> bool:
 3        stack = []
 4        mapping = {"}": "{", "]": "[", ")": "("}
 5
 6        if len(s) % 2 == 1:
 7            return False
 8        
 9        for c in s:
10            if c in mapping:
11                if not stack or stack[-1] != mapping[c]:
12                    return False
13                stack.pop()
14            else:
15                stack.append(c)
16        
17        return not stack

复杂度：

时间 O(n)：每个字符入栈出栈至多一次
空间 O(n)：最坏全是左括号

2.2 字符串解码 | Medium

题目：解码 k[encoded_string] 格式："3[a2[c]]" → "accaccacc"。k 保证为正整数，可嵌套

思路分析：

嵌套结构 = 栈。遇到[时，当前的进度（已经拼好的字符串 + 待用倍数）需要挂起，等内层解码完再回来，此时需要压栈保存现场

维护 cur（当前层已解码串）和 num(当前累积的倍数)
数字：num = num * 10 + int(c)
字母：cur += c
[：将当前状况(cur, k)压栈，二者清零然后重新开始内层
]：弹出(prev, k)，cur = prev + cur * k

踩坑记录：

多位数字处理方法：100[c] ，k = 100 $\Rightarrow$ num = num * 10 + int(c)
遇 [ 后忘记把 num 清零，导致下一个数字被污染

代码：

 1class Solution:
 2    def decodeString(self, s: str) -> str:
 3        stack = []
 4        cur, num = "", 0
 5
 6        for c in s:
 7            if c.isdigit():
 8                num = num * 10 + int(c)
 9            elif c == "[":
10                stack.append((cur, num))
11                cur, num = "", 0
12            elif c == "]":
13                prev, k = stack.pop()
14                cur = prev + cur * k
15            else:
16                cur += c
17
18        return cur

复杂度：

时间 O(S)：S 为解码后字符串长度（展开操作的总代价）
空间 O(S)：栈 + 结果串

3 表达式求职

3.1 逆波兰表达式求值 | Medium

题目：求后缀表达式（RPN）的值，如 ["2","1","+","3","*"] = (2+1)*3 = 9。除法向零截断。

思路分析：

数字：入栈
符号：弹出两个操作数（先弹出来的是右操作数）计算后入栈

几种表达式写法：

中缀：a + b
前序（波兰式）：+ a b
逆序（逆波兰式）：a b +

踩坑记录：

注意操作数顺序，先弹出的是右操作数
int()/floor()/ceil()/round()区别：向0靠近/向负无穷靠近/向正无穷靠近/最近偶数

代码：

 1class Solution:
 2    def evalRPN(self, tokens: List[str]) -> int:
 3		ops = {
 4			"+": lambda a, b: a + b,
 5			"-": lambda a, b: a - b,
 6			"*": lambda a, b: a * b,
 7			"/": lambda a, b: int(a / b)
 8		}
 9        stack = []
10
11        for t in tokens:
12            if t in ops:
13                b = stack.pop()
14                a = stack.pop()
15				stack.append(ops[t](a, b))
16            else:
17                stack.append(int(t))
18        
19        return stack[0]

 1class Solution:
 2    def evalRPN(self, tokens: List[str]) -> int:
 3        ops = {
 4			"+": lambda a, b: a + b,
 5			"-": lambda a, b: a - b,
 6			"*": lambda a, b: a * b,
 7			"/": lambda a, b: int(a / b)
 8		}
 9        stack = []
10
11        for t in tokens:
12            if t in ops:
13                b = stack.pop()
14                a = stack.pop()
15                stack.append(ops[t](a, b))
16            else:
17                stack.append(int(t))
18        
19        return stack[0]

复杂度：

时间 O(n)：每个 token 处理一次
空间 O(n)：栈中最多存约 n/2 个操作数

3.2 基本计算器 II | Medium

题目：计算只含非负整数、+ - * / 和空格的中缀表达式，除法向零截断。如 "3+2*2" = 7

思路分析：中缀运算具有优先级：乘除要先算

维护num（当前累计的数字）和sign（上一个运算符，初始为"+"）
每次遇到新的运算符或者扫到末尾，说明num算完了：
- sign == +：num入栈
- sign == -：-num入栈
- sign == * or /：弹出栈顶与num计算再压回
最后栈中全是不被乘除影响的加法项

踩坑记录：

注意算最后一个数字
空格直接跳过

代码：

 1class Solution:
 2    def calculate(self, s: str) -> int:
 3        stack = []
 4        sign, num = "+", 0
 5
 6        for i, c in enumerate(s):
 7            if c.isdigit():
 8                num = num * 10 + int(c)
 9            if c in "+-*/" or i == len(s) - 1:
10                if sign == "+":
11                    stack.append(num)
12                elif sign == "-":
13                    stack.append(-num)
14                elif sign == "*":
15                    stack.append(stack.pop() * num)
16                else:
17                    stack.append(int(stack.pop() / num))
18                sign, num = c, 0
19        
20        return sum(stack)

复杂度：

时间 O(n)：单遍扫描
空间 O(n)：栈存加法项

4 单调栈

单调栈一句话：栈内元素保持单调，新元素入栈前，把「被它终结」的栈顶元素弹出并结算答案
适用信号：找每个元素左边/右边第一个比它大/小的元素 → 暴力 O(n²)，单调栈 O(n)
方向口诀（栈底→栈顶）：
找下一个更大 → 维护单调递减栈（新来的大元素把小的都"打败"弹出）
找下一个更小 → 维护单调递增栈
存下标而非值：既能算距离，又能通过下标取值，信息无损

1for i, t in enumerate(nums):
2    while stack and 栈顶该被t结算:
3        j = stack.pop()
4        结算 j
5    stack.append(i)

4.1 下一个更大元素 I | Medium

题目：nums1 是 nums2 的子集（元素互不相同）。对 nums1 中每个 x，找它在 nums2 中同位置右侧第一个更大元素，不存在为 -1

思路分析：

对 nums2 跑一遍单调栈，把每个元素的下一个更大元素存入哈希表（元素互不相同，可以直接用值作 key）
nums1 逐个查表

踩坑记录：因为没有重复的元素所以用哈希表，如果有重复的一般存下标

代码：

 1class Solution:
 2    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
 3        next = {}
 4        stack = []
 5
 6        for num in nums2:
 7            while stack and stack[-1] < num:
 8                next[stack.pop()] = num
 9            stack.append(num)
10        
11        return [next.get(num, -1) for num in nums1]

复杂度：

时间 O(n)：单遍扫描
空间 O(n)：栈存加法项

4.2 下一个更大元素 II | Medium

题目：循环数组中找每个元素的下一个更大元素（可绕回开头找），不存在为 -1

思路分析：循环数组的经典技巧：逻辑上把数组复制一份接在后面，遍历 2n 次

stack存下标
下标需要i % n取模
第二圈不需要入栈了，只给第一圈打补丁（没找到最大元素的）

踩坑记录：

不需要真的拼接，直接取模
答案初始化为-1
第二圈仍然 append 且不做限制：不影响结果（栈里的重复下标不会产生错误结算），但要想清楚为什么

代码：

 1class Solution:
 2    def nextGreaterElements(self, nums: List[int]) -> List[int]:
 3        n = len(nums)
 4        ans = [-1] * n
 5        stack = []
 6
 7        for i in range(2 * n):
 8            num = nums[i % n]
 9            while stack and nums[stack[-1]] < num:
10                ans[stack.pop()] = num
11            if i < n:
12                stack.append(i)
13        
14        return ans

复杂度：

时间 O(n)：遍历 2n 次，每个下标入栈出栈至多一次
空间 O(n)：栈

4.3 每日温度 | Medium

题目：给定每日温度数组，返回 answer[i] = 第 i 天后要等几天才有更高温度，等不到则为 0

思路分析：

依旧是找右边的第一个更大的元素的距离，这里维护一个存下标、温度递减的单调栈

新的温度T[i]到来：比栈顶温度高，栈顶那天的答案确定，重复循环
最后将该天温度入栈

踩坑记录：

栈需要存下标，才能算距离
初始化为0

代码：

 1class Solution:
 2    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
 3        n = len(temperatures)
 4        ans = [0] * n
 5        stack = []
 6
 7        for i, t in enumerate(temperatures):
 8            while stack and temperatures[stack[-1]] < t:
 9                j = stack.pop()
10                ans[j] = i - j
11            stack.append(i)
12        
13        return ans

复杂度：

时间 O(n)：每个下标至多入栈出栈一次
空间 O(n)：最坏温度单调递减，全部驻留栈中

4.4 柱状图中最大的矩形 | Medium

题目：n 个宽为 1 的柱子，高度为 heights[i]，求能勾勒出的最大矩形面积

思路分析：

换个视角：枚举「以每根柱子 i 为最矮柱（高度瓶颈）」的矩形。此时矩形能向左右延伸到：

左边界 L：i 左侧第一个更矮的柱子（不含）
右边界 R：i 右侧第一个更矮的柱子（不含）
面积 = heights[i] * (R - L - 1)

「左右第一个更小」→ 单调递增栈。当 heights[i] < 栈顶 时，栈顶柱子的右边界确定为 i，左边界是弹出后的新栈顶，当场结算面积。

踩坑记录：

注意加一个哨兵
计算宽度和高度
弹栈条件

代码：

 1class Solution:
 2    def largestRectangleArea(self, heights: List[int]) -> int:
 3        heights.append(0)
 4        stack = []
 5        best = 0
 6
 7        for i, h in enumerate(heights):
 8            while stack and heights[stack[-1]] > h:
 9                height = heights[stack.pop()]
10                left = stack[-1] if stack else -1
11                width = i - left - 1
12                best = max(best, width * height)
13            stack.append(i)
14        
15        return best

复杂度：

时间 O(n)：每根柱子入栈出栈一次
空间 O(n)：栈

0 Stack Basic#

1 栈的设计与模拟#

2 匹配 / 保存现场栈#

3 表达式求职#

4 单调栈#

0 Stack Basic

1 栈的设计与模拟

2 匹配 / 保存现场栈

3 表达式求职

4 单调栈