第3讲：栈（Stack）

第3讲：栈（Stack）

目标：让完全没学过编程的人，也能理解栈的本质，并亲手用Python跑代码验证。

一、先讲个故事：为什么叫"栈"？

场景：食堂的餐盘

你去食堂吃饭，看到放餐盘的地方：

┌─────┐ ← 最上面 (栈顶) │ 盘子3 │ ├─────┤ │ 盘子2 │ ├─────┤ │ 盘子1 │ ├─────┤ │ 盘子0 │ ← 最下面 (栈底) └─────┘

规则：

• 放盘子：只能放在最上面 (push)
• 拿盘子：只能拿最上面的 (pop)
• 看最上面：看看最上面是什么，但不拿 (peek)

核心特点：后放的先拿，先放的后拿

这就是LIFO=LastInFirstOut (后进先出)

生活中的栈

二、栈的基本操作

2.1 四个基本操作

初始: 空栈 [] push(10): [10] ↑栈顶 push(20): [10, 20] ↑栈顶 push(30): [10, 20, 30] ↑栈顶 peek(): 看到 30 (最上面), 但不拿 [10, 20, 30] ↑栈顶 pop(): 拿走 30 [10, 20] ↑栈顶 pop(): 拿走 20 [10] ↑栈顶 pop(): 拿走 10 [] 空栈!

2.2 Python实现

classStack:def__init__(self):self.items=[]defpush(self,item):"""放东西到栈顶"""self.items.append(item)print(f"push({item}):{self.items}")defpop(self):"""从栈顶拿东西"""ifself.is_empty():print("pop(): 栈空了! 拿不了")returnNoneitem=self.items.pop()print(f"pop(): 拿走{item}, 剩余{self.items}")returnitemdefpeek(self):"""看栈顶, 但不拿"""ifself.is_empty():returnNonereturnself.items[-1]defis_empty(self):"""栈是不是空的"""returnlen(self.items)==0defsize(self):"""栈里有多少东西"""returnlen(self.items)# 测试stack=Stack()stack.push(10)stack.push(20)stack.push(30)print(f"当前栈顶:{stack.peek()}")print(f"栈大小:{stack.size()}")stack.pop()stack.pop()stack.pop()stack.pop()# 再拿就空了

三、栈与递归的关系

3.1 递归是什么？

递归 = 函数自己调用自己。但底层是怎么实现的？用栈！

3.2 例子：计算 3!

3! = 3 × 2! 2! = 2 × 1! 1! = 1 × 0! 0! = 1

调用栈的变化：

调用 factorial(3): 栈: [factorial(3)] 需要 factorial(2): 栈: [factorial(3), factorial(2)] 需要 factorial(1): 栈: [factorial(3), factorial(2), factorial(1)] 需要 factorial(0): 栈: [factorial(3), factorial(2), factorial(1), factorial(0)] factorial(0) 返回 1: 栈: [factorial(3), factorial(2), factorial(1)] ← 弹出! factorial(1) 返回 1×1 = 1: 栈: [factorial(3), factorial(2)] ← 弹出! factorial(2) 返回 2×1 = 2: 栈: [factorial(3)] ← 弹出! factorial(3) 返回 3×2 = 6: 栈: [] ← 弹出! 完成!

3.3 代码验证

call_stack=[]deffactorial(n):call_stack.append(f"factorial({n})")print(f" 进入 factorial({n}), 调用栈:{call_stack}")ifn<=1:result=1print(f" factorial({n}) = 1 (基准情况)")else:result=n*factorial(n-1)print(f" factorial({n}) ={n}×{result//n}={result}")call_stack.pop()print(f" 退出 factorial({n}), 调用栈:{call_stack}")returnresult result=factorial(3)print(f"最终结果: 3! ={result}")

关键发现：递归的"先调用后返回"，本质上就是栈的 LIFO！

四、单调栈：寻找下一个更大元素

4.1 什么是单调栈？

单调栈 = 栈里的元素保持单调递增(或递减)。

经典问题：给定数组，找每个元素右边第一个比它大的数。

数组: [73, 74, 75, 71, 69, 72, 76, 73] 问: 第0天(73度), 过几天会升温? 答: 第1天(74度)就升温了, 等1天 问: 第3天(71度), 过几天会升温? 答: 第5天(72度)才升温, 等2天

4.2 单调栈原理

核心思想：维护一个"从栈底到栈顶递减"的栈。

第0天 73度: 栈空, 直接入栈 栈: [(0, 73)] 第1天 74度: 74 > 栈顶73, 73找到了答案! 弹出(0, 73): 答案 = 1-0 = 1天 入栈(1, 74) 栈: [(1, 74)] 第2天 75度: 75 > 栈顶74, 74找到了答案! 弹出(1, 74): 答案 = 2-1 = 1天 入栈(2, 75) 栈: [(2, 75)] 第3天 71度: 71 < 栈顶75, 不知道答案, 入栈等待 栈: [(2, 75), (3, 71)] 第4天 69度: 69 < 栈顶71, 不知道答案, 入栈等待 栈: [(2, 75), (3, 71), (4, 69)] 第5天 72度: 72 > 栈顶69, 69找到了答案! 弹出(4, 69): 答案 = 5-4 = 1天 72 > 栈顶71, 71也找到了答案! 弹出(3, 71): 答案 = 5-3 = 2天 72 < 栈顶75, 不知道答案, 入栈等待 栈: [(2, 75), (5, 72)] 第6天 76度: 76 > 栈顶72, 72找到了答案! 弹出(5, 72): 答案 = 6-5 = 1天 76 > 栈顶75, 75也找到了答案! 弹出(2, 75): 答案 = 6-2 = 4天 入栈(6, 76) 栈: [(6, 76)] 第7天 73度: 73 < 栈顶76, 不知道答案, 入栈等待 栈: [(6, 76), (7, 73)] 遍历结束, 栈里剩余的都没找到答案, 填0

4.3 代码实现

defdaily_temperatures(temperatures):n=len(temperatures)answer=[0]*n stack=[]# 存 (索引, 温度), 栈底到栈顶递减fori,tempinenumerate(temperatures):# 当前温度比栈顶高? 说明栈顶找到了答案!whilestackandtemp>stack[-1][1]:prev_idx,prev_temp=stack.pop()wait_days=i-prev_idx answer[prev_idx]=wait_daysprint(f" 栈顶(第{prev_idx}天,{prev_temp}度)等到了! 等{wait_days}天")stack.append((i,temp))print(f" 入栈等待")returnanswer temps=[73,74,75,71,69,72,76,73]result=daily_temperatures(temps)print(f"最终结果:{result}")

核心思想：栈里存的是"还没找到答案的元素"。遇到更高的，就帮栈里的元素"找到答案"然后弹出。

五、LeetCode实战

🔥 题目1：有效的括号（LC 20）

题目：给定一个只包含()[]{}的字符串，判断是否有效。

解法：栈匹配

defis_valid(s):stack=[]pairs={')':'(',']':'[','}':'{'}forcharins:ifcharin'([{':stack.append(char)print(f"左括号, 入栈 → 栈:{stack}")else:ifnotstack:returnFalsetop=stack.pop()iftop!=pairs[char]:returnFalseprint(f"右括号, 和栈顶'{top}'匹配! 弹出")returnlen(stack)==0# 测试print(is_valid("()"))# Trueprint(is_valid("()[]{}"))# Trueprint(is_valid("(]"))# False

核心：最后开的括号最先关，符合LIFO！

🔥 题目2：最小栈（LC 155）

题目：设计一个栈，支持 push, pop, top，并且能在 O(1) 获取最小值。

解法：辅助栈

classMinStack:def__init__(self):self.stack=[]# 主栈self.min_stack=[]# 辅助栈(存最小值)defpush(self,val):self.stack.append(val)ifnotself.min_stack:self.min_stack.append(val)else:self.min_stack.append(min(val,self.min_stack[-1]))defpop(self):self.stack.pop()self.min_stack.pop()deftop(self):returnself.stack[-1]defgetMin(self):returnself.min_stack[-1]# 测试min_stack=MinStack()min_stack.push(-2)min_stack.push(0)min_stack.push(-3)print(min_stack.getMin())# -3min_stack.pop()print(min_stack.getMin())# -2

核心：辅助栈的每个位置，记录"以当前位置为栈顶时的最小值"。

🔥 题目3：每日温度（LC 739）

已在上面"单调栈原理"部分详细讲解。

🔥 题目4：柱状图中最大的矩形（LC 84）

题目：给定柱状图，找其中能构成的最大矩形面积。

解法：单调栈

deflargest_rectangle_area(heights):heights=[0]+heights+[0]# 两边加0n=len(heights)stack=[]max_area=0foriinrange(n):whilestackandheights[i]<heights[stack[-1]]:h=heights[stack.pop()]left=stack[-1]width=i-left-1area=h*width max_area=max(max_area,area)stack.append(i)returnmax_area heights=[2,1,5,6,2,3]print(largest_rectangle_area(heights))# 10

🔥 题目5：字符串解码（LC 394）

题目：给定编码字符串，返回解码结果。

解法：栈处理嵌套

defdecode_string(s):stack=[]# 存 (之前的字符串, 重复次数)current_str=""num=0forcharins:ifchar.isdigit():num=num*10+int(char)elifchar=='[':stack.append((current_str,num))current_str,num="",0elifchar==']':prev_str,repeat=stack.pop()current_str=prev_str+current_str*repeatelse:current_str+=charreturncurrent_str# 测试print(decode_string("3[a]"))# "aaa"print(decode_string("3[a2[c]]"))# "accaccacc"

核心：栈用来保存"上一层的状态"，遇到[就入栈保存，遇到]就弹出恢复，完美处理嵌套！

六、本讲总结

🧠 核心要点

1. 栈的本质：LIFO (后进先出)，像食堂的餐盘
2. 基本操作：push(入栈), pop(出栈), peek(看栈顶)
3. 递归的底层：函数调用栈，先调用后返回
4. 单调栈：维护单调性，帮栈内元素"找到答案"
5. 辅助栈：用额外栈保存额外信息(如最小值)

📝 面试高频问题

🎯 下节预告

第4讲：队列—— FIFO特性与滑动窗口，以及BFS、单调队列等经典应用。

💪课后作业：

1. 把本讲所有代码亲手跑一遍
2. 去 LeetCode 做 LC 20, LC 155, LC 739, LC 84, LC 394
3. 思考：还有哪些问题可以用单调栈解决？