第3讲：栈（Stack）

第3讲栈Stack目标让完全没学过编程的人也能理解栈的本质并亲手用Python跑代码验证。一、先讲个故事为什么叫栈场景食堂的餐盘你去食堂吃饭看到放餐盘的地方┌─────┐ ← 最上面 (栈顶) │ 盘子3 │ ├─────┤ │ 盘子2 │ ├─────┤ │ 盘子1 │ ├─────┤ │ 盘子0 │ ← 最下面 (栈底) └─────┘规则放盘子只能放在最上面 (push)拿盘子只能拿最上面的 (pop)看最上面看看最上面是什么但不拿 (peek)核心特点后放的先拿先放的后拿这就是LIFOLastInFirstOut (后进先出)生活中的栈场景为什么像栈浏览器后退最后访问的页面最先退回去撤销操作(CtrlZ)最后做的操作最先撤销括号匹配最后开的括号最先关函数调用最后调用的函数最先返回二、栈的基本操作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(fpush({item}):{self.items})defpop(self):从栈顶拿东西ifself.is_empty():print(pop(): 栈空了! 拿不了)returnNoneitemself.items.pop()print(fpop(): 拿走{item}, 剩余{self.items})returnitemdefpeek(self):看栈顶, 但不拿ifself.is_empty():returnNonereturnself.items[-1]defis_empty(self):栈是不是空的returnlen(self.items)0defsize(self):栈里有多少东西returnlen(self.items)# 测试stackStack()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(ffactorial({n}))print(f 进入 factorial({n}), 调用栈:{call_stack})ifn1:result1print(f factorial({n}) 1 (基准情况))else:resultn*factorial(n-1)print(f factorial({n}) {n}×{result//n}{result})call_stack.pop()print(f 退出 factorial({n}), 调用栈:{call_stack})returnresult resultfactorial(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)] 遍历结束, 栈里剩余的都没找到答案, 填04.3 代码实现defdaily_temperatures(temperatures):nlen(temperatures)answer[0]*n stack[]# 存 (索引, 温度), 栈底到栈顶递减fori,tempinenumerate(temperatures):# 当前温度比栈顶高? 说明栈顶找到了答案!whilestackandtempstack[-1][1]:prev_idx,prev_tempstack.pop()wait_daysi-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]resultdaily_temperatures(temps)print(f最终结果:{result})核心思想栈里存的是还没找到答案的元素。遇到更高的就帮栈里的元素找到答案然后弹出。五、LeetCode实战 题目1有效的括号LC 20题目给定一个只包含()[]{}的字符串判断是否有效。解法栈匹配defis_valid(s):stack[]pairs{):(,]:[,}:{}forcharins:ifcharin([{:stack.append(char)print(f左括号, 入栈 → 栈:{stack})else:ifnotstack:returnFalsetopstack.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_stackMinStack()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]# 两边加0nlen(heights)stack[]max_area0foriinrange(n):whilestackandheights[i]heights[stack[-1]]:hheights[stack.pop()]leftstack[-1]widthi-left-1areah*width max_areamax(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_strnum0forcharins:ifchar.isdigit():numnum*10int(char)elifchar[:stack.append((current_str,num))current_str,num,0elifchar]:prev_str,repeatstack.pop()current_strprev_strcurrent_str*repeatelse:current_strcharreturncurrent_str# 测试print(decode_string(3[a]))# aaaprint(decode_string(3[a2[c]]))# accaccacc核心栈用来保存上一层的状态遇到[就入栈保存遇到]就弹出恢复完美处理嵌套六、本讲总结 核心要点栈的本质LIFO (后进先出)像食堂的餐盘基本操作push(入栈), pop(出栈), peek(看栈顶)递归的底层函数调用栈先调用后返回单调栈维护单调性帮栈内元素找到答案辅助栈用额外栈保存额外信息(如最小值) 面试高频问题问题答案栈和队列的区别?栈LIFO(后进先出)队列FIFO(先进先出)递归为什么用栈实现?先调用的函数后返回符合LIFO单调栈解决什么问题?找下一个更大/更小元素最小栈怎么实现O(1)?辅助栈每个位置存当前最小值括号匹配为什么用栈?最后开的括号最先关符合LIFO 下节预告第4讲队列—— FIFO特性与滑动窗口以及BFS、单调队列等经典应用。课后作业把本讲所有代码亲手跑一遍去 LeetCode 做 LC 20, LC 155, LC 739, LC 84, LC 394思考还有哪些问题可以用单调栈解决