栈与单调栈基础原理与题目说明

栈与单调栈基础原理与题目说明文章目录栈与单调栈基础原理与题目说明一、 什么是栈Stack1.1 核心操作与限制1.2 经典应用场景二、 基础栈的应用实战[20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/)[155. 最小栈](https://leetcode.cn/problems/min-stack/)[394. 字符串解码](https://leetcode.cn/problems/decode-string/)[19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)三、 进阶单调栈Monotonic Stack[739. 每日温度](https://leetcode.cn/problems/daily-temperatures/)[84. 柱状图中最大的矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram/) 查看完整专栏LeetCode基础算法专栏特别说明本文为个人的 LeetCode 刷题与学习笔记内容仅供学习与交流使用禁止转载或用于商业用途。需要强调的是文中的题目解法不一定是最优解可能存在时间或空间复杂度的进一步优化空间主要目的是分享个人的解题思路与逻辑实现仅供参考。笔记内容为个人理解与总结可能存在疏漏或偏差欢迎读者自行甄别并交流探讨。一、 什么是栈Stack栈是一种特殊的线性数据结构其最核心的特点是后进先出LIFO, Last In First Out。可以将其想象成一个只能从顶端放入和取出的桶最先放入底部的物品只能等到上面的物品全被取走后才能取出。1.1 核心操作与限制操作指令push(x)将元素压入栈顶。pop()弹出并返回栈顶元素。top()/peek()仅查看栈顶元素不弹出。物理限制只能访问栈顶元素无法直接访问栈中间或栈底的元素。不支持在两端同时进行操作区别于双端队列 Deque。1.2 经典应用场景普通栈括号匹配、系统调用栈递归、字符串解码、利用“先进后出”特性反转数据如链表倒序。单调栈专门用于求解序列中的下一个更大 / 更小元素等一维极值问题。二、 基础栈的应用实战20. 有效的括号题目描述给定一个只包括(){}[]的字符串s判断字符串是否有效。有效条件左括号必须用相同类型的右括号按正确顺序闭合。解题思路典型的“后进先出”场景最后遍历到的左括号最先要判断匹配的右括号。用哈希表存储左括号 - 右括号的映射方便快速查找与比对。遍历字符串遇到左括号直接入栈遇到右括号则检查栈顶是否为对应的左括号。若栈为空或括号不匹配直接返回False遍历结束后栈必须为空才算完全匹配。核心代码classSolution:defisValid(self,s:str)-bool:stack[]hashmap{(:),{:},[:]}forcharins:# 1. 左括号直接入栈ifcharinhashmap:stack.append(char)# 2. 右括号开始匹配栈顶else:# 栈已空无左括号匹配ifnotstack:returnFalseleft_charstack.pop()# 左右括号不匹配ifchar!hashmap[left_char]:returnFalse# 3. 遍历结束栈内仍有残留左括号则无效returnnotstack155. 最小栈题目描述设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。解题思路要使每个元素与其对应的最小值时刻保持一一对应可以使用一个辅助栈。辅助栈与数据主栈同步插入与删除且辅助栈的栈顶永远维护当前主栈的最小值。Push主栈正常压入辅助栈压入min(当前值, 辅助栈顶值)。Pop主栈和辅助栈同步弹出。核心代码importmathclassMinStack:def__init__(self):self.stack[]# 辅助栈初始化放入无穷大方便后续取最小值self.min_stack[math.inf]defpush(self,val:int)-None:self.stack.append(val)# 辅助栈压入当前历史最小值self.min_stack.append(min(val,self.min_stack[-1]))defpop(self)-None:self.stack.pop()self.min_stack.pop()deftop(self)-int:returnself.stack[-1]defgetMin(self)-int:returnself.min_stack[-1]394. 字符串解码题目描述给定一个经过编码的字符串返回它解码后的字符串。编码规则为:k[encoded_string]表示方括号内部的encoded_string正好重复k次。解题思路遇到嵌套问题优先考虑栈。遇到[时说明遇到了新的内部上下文需要保存之前的状态。遇到数字计算多位数字倍数k。遇到[将之前的(临时字符串, 倍数k)压入栈重置临时变量。遇到]从栈中弹出之前的状态进行字符串拼接prev_str res * k。遇到字母直接追加到当前临时字符串上。核心代码classSolution:defdecodeString(self,s:str)-str:stack[]num0resforcins:if0c9:# 累加多位数字numnum*10int(c)elifc[:# 入栈保存上下文状态stack.append((res,num))resnum0elifc]:# 出栈进行拼接解码prev_str,kstack.pop()resprev_strres*kelse:rescreturnres19. 删除链表的倒数第 N 个结点解题思路本题主流解法是快慢指针但利用栈的“先进后出”特性也是绝佳思路遍历一次链表将所有节点压入栈随后弹出n个节点此时栈顶就是待删除节点的前驱节点。引入**虚拟头节点Dummy Node**可以完美避免删除原始头节点时的越界报错。核心代码fromtypingimportOptional# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defremoveNthFromEnd(self,head:Optional[ListNode],n:int)-Optional[ListNode]:# 虚拟头节点处理删除原始头节点的边界dummy_nodeListNode(0,head)stack[]# 遍历链表所有节点入栈currentdummy_nodewhilecurrent:stack.append(current)currentcurrent.next# 弹出后续的 n 个节点for_inrange(n):stack.pop()# 此时栈顶即为待删除节点的前驱直接修改 next 指针pre_nodestack[-1]pre_node.nextpre_node.next.nextreturndummy_node.next三、 进阶单调栈Monotonic Stack单调栈是一种特殊的栈它在保持栈的“先进后出”特性的同时要求栈内元素必须保持单调递增或单调递减。适用场景一维数组中寻找下一个更大、下一个更小元素等位置关联问题。739. 每日温度题目描述给定一个整数数组temperatures表示每天的温度返回一个数组answer其中answer[i]是指对于第i天下一个更高温度出现在几天后。解题思路采用单调递减栈栈中维护未找到更高温度的(下标, 温度)元组。遍历温度数组时若当前温度 栈顶温度说明栈顶元素等到了它的“下一个更高温度”弹出栈顶并计算天数差当前下标 - 栈顶下标。持续此过程直至栈为空或不满足条件。将当前(下标, 温度)入栈等待后续更高的温度。核心代码fromtypingimportListclassSolution:defdailyTemperatures(self,temperatures:List[int])-List[int]:# 维护一个递减栈存放 (idx, tmp)stack[]ans[0]*len(temperatures)foriinrange(len(temperatures)):cur_idxi cur_tmptemperatures[i]# 栈不空且当前温度 栈顶温度触发结算whilestackandcur_tmpstack[-1][1]:idx,tmpstack.pop()ans[idx]cur_idx-idx# 当前元素入栈等待判定stack.append((cur_idx,cur_tmp))returnans84. 柱状图中最大的矩形题目描述给定n nn个非负整数用来表示柱状图中各个柱子的高度。每个柱子宽度为 1。求在该柱状图中能够勾勒出来的矩形的最大面积。解题思路这是一道非常经典的单调栈 Hard 题。求矩形面积的核心是找到当前柱子左右两侧第一个比它矮的柱子这样才能确定矩形的宽度边界。采用单调递增栈栈内存下标遍历数组当发现当前柱子高度栈顶柱子高度时说明栈顶柱子的“右侧第一个更矮柱子”找到了。此时弹出栈顶柱子计算以它为高度的矩形面积其左边界即为弹出后的新栈顶右边界即为当前遍历到的柱子。技巧首尾哨兵在原数组头部和尾部各补一个0。头部补0避免栈空时的越界尾部补0强制在遍历最后弹出所有剩余的柱子进行计算。核心代码fromtypingimportListclassSolution:deflargestRectangleArea(self,heights:List[int])-int:# 首尾补 0# 首 0 保证栈永远不空方便计算宽度# 尾 0 保证遍历结束时能强制弹出栈内所有有效元素并计算面积heights[0]heights[0]stack[]# 存储下标维持单调递增ans0foriinrange(len(heights)):# 当前高度小于栈顶高度破坏了单调递增说明找到了栈顶柱子的右边界whilestackandheights[i]heights[stack[-1]]:# 1. 取出要计算的柱子高度cur_heightheights[stack.pop()]# 2. 此时新的栈顶就是它的左边界开区间i 是它的右边界开区间leftstack[-1]righti# 3. 计算宽度并更新最大面积cur_widthright-left-1ansmax(ans,cur_height*cur_width)# 当前下标入栈stack.append(i)returnans