力扣hot100—系列6-栈
栈（Stack）的逻辑核心是 后进先出（LIFO, Last In First Out）。在处理具有“嵌套”、“匹配”或“寻找最近一个更大/更小”这类问题时，栈是非常强大的工具。
1. 有效的括号 (LeetCode 20)
核心思想：匹配消消乐。
- 直观思路：
- 遍历字符串，遇到左括号
([{就入栈。 - 遇到右括号
)]}，就看栈顶是不是对应的左括号。 - 如果是，就“抵消”（出栈）；如果不是或者栈空了，说明非法。
- 最后如果栈空了，说明全部匹配成功。
- 遍历字符串，遇到左括号
- 复杂度： 时间 O(N)O(N)O(N)，空间 O(N)O(N)O(N)。
代码实现 (Python):
defisValid(s:str)->bool: stack =[]# 使用哈希表建立对应关系，方便查询 mapping ={")":"(","]":"[","}":"{"}for char in s:if char in mapping:# 如果是右括号，弹出栈顶元素，看是否匹配 top_element = stack.pop()if stack else'#'if mapping[char]!= top_element:returnFalseelse:# 如果是左括号，入栈 stack.append(char)returnnot stack # 栈为空则有效2. 最小栈 (LeetCode 155)
核心思想：同步辅助栈。
- 直观思路：
- 普通的栈无法在 O(1)O(1)O(1) 时间内找到最小值，因为最小值可能被压在下面。
- 解决： 准备一个辅助栈
min_stack，它和主栈同步。 - 辅助栈的每个位置存：“主栈从底部到当前位置为止的最小值”。
- 这样，无论主栈怎么弹出，辅助栈的顶部永远是当前剩下的数里的最小值。
- 复杂度：O(1)O(1)O(1) 时间完成所有操作。
代码实现 (Python):
classMinStack:def__init__(self): self.stack =[] self.min_stack =[]defpush(self, val:int)->None: self.stack.append(val)# 如果辅助栈为空，或者新值更小，则压入新值# 否则，再次压入当前辅助栈的栈顶（保持同步）ifnot self.min_stack or val < self.min_stack[-1]: self.min_stack.append(val)else: self.min_stack.append(self.min_stack[-1])defpop(self)->None: self.stack.pop() self.min_stack.pop()deftop(self)->int:return self.stack[-1]defgetMin(self)->int:return self.min_stack[-1]3. 字符串解码 (LeetCode 394)
核心思想：遇到 [ 压入现场，遇到 ] 恢复现场。
- 直观思路：
- 比如
3[a2[c]]。我们需要处理嵌套。 - 遇到数字：计算倍数。
- 遇到字符：拼接到当前结果。
- 遇到
[： 说明进入了内部层级。要把当前的字符串和当前的倍数一起压入栈中，然后重置它们，开始处理括号内部。 - 遇到
]： 说明内部层级结束。从栈里弹出“外层的字符串”和“倍数”，把当前内部的结果重复 N 次后接在外层字符串后面。
- 比如
- 复杂度： 时间 O(S)O(S)O(S)，空间 O(S)O(S)O(S)（S 是解码后的长度）。
代码实现 (Python):
defdecodeString(s:str)->str: stack =[]# 存储 (当前字符串, 当前倍数) curr_str ="" curr_num =0for char in s:if char.isdigit(): curr_num = curr_num *10+int(char)elif char =='[':# 记录现场：把之前的字符串和数字压栈 stack.append((curr_str, curr_num)) curr_str, curr_num ="",0# 重置elif char ==']':# 恢复现场 last_str, num = stack.pop() curr_str = last_str + num * curr_str else: curr_str += char return curr_str 4. 每日温度 (LeetCode 739)
核心思想：单调栈（Monotonic Stack）。
- 直观思路：
- 我们要找“右边第一个比我大的数”。
- 遍历数组，如果当前温度比栈顶的温度高，说明栈顶那些人在“等”的更高温终于来了！
- 不断弹出栈顶，并计算天数差（当前索引 - 栈顶索引）。
- 如果当前温度低，就入栈等待。
- 栈内特点： 存的是下标，对应的温度从栈底到栈顶是递减的。
- 复杂度： 时间 O(N)O(N)O(N)（每个元素只进出栈一次）。
代码实现 (Python):
defdailyTemperatures(temperatures): n =len(temperatures) res =[0]* n stack =[]# 存放下标for i inrange(n):# 如果当前温度大于栈顶下标对应的温度while stack and temperatures[i]> temperatures[stack[-1]]: prev_index = stack.pop() res[prev_index]= i - prev_index stack.append(i)return res 5. 柱状图中最大的矩形 (LeetCode 84)
核心思想：单调栈（找左右边界）。
- 直观思路：
- 对于每一根柱子，以它的高度为矩形的高度，能向左右延伸多远？
- 延伸的边界是：左右两边第一个比它矮的柱子。
- 我们维护一个单调递增栈：
- 如果当前柱子比栈顶高，入栈。
- 如果当前柱子比栈顶矮，说明栈顶柱子的右边界找到了。
- 栈顶柱子弹出来，它左边的边界就是现在的栈顶。
- 技巧： 在数组开头和结尾加一个高度为
0的“哨兵”，确保所有柱子都能被计算。
- 复杂度： 时间 O(N)O(N)O(N)。
代码实现 (Python):
deflargestRectangleArea(heights):# 加哨兵，简化边界处理 heights =[0]+ heights +[0] stack =[] max_area =0for i inrange(len(heights)):# 如果当前高度小于栈顶高度，开始结算while stack and heights[i]< heights[stack[-1]]: h = heights[stack.pop()]# 以弹出的柱子作为高度# 此时新的栈顶是左边界，i 是右边界 w = i - stack[-1]-1 max_area =max(max_area, h * w) stack.append(i)return max_area 第一次刷题的避坑总结：
- 什么时候用栈？ 题目有“匹配”、“最近相关性”、“逆序输出”、“撤销操作”等关键词时。
- 什么是单调栈？ 专门解决“寻找左/右边第一个比我大/小的元素”。
- 下标 or 数值？ 在单调栈题目（如温度、矩形）中，通常栈里存的是下标，因为下标既能找到数值，又能计算距离。
- 哨兵位： 像“矩形”这类题，加个
0可以避免处理遍历完后栈内还有残留元素的情况，非常实用。
