栈

题目要求 设计一个栈 MinStack，支持以下操作： MinStack()：初始化栈。 push(value)：把 value 压入栈顶。 pop()：删除栈顶元素。 top()：返回栈顶元素。 getMin()：返回栈中的最小元素。 题目要求每个操作的时间复杂度都是 O(1)。 pop、top 和 getMin 只会在栈非空时调用，因此不需要为这些方法设计额外的空栈返回值。 示例 输入操作： ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"] 输入参数： [[], [-2], [0], [-3], [], [], [], []] 输出： [null, null, null, null, -3, null, 0, -2] 对应的执行过程是： min_stack = MinStack() min_stack.push(-2) min_stack.push(0) min_stack.push(-3) min_stack.getMin() # -3 min_stack.pop() min_stack.top() # 0 min_stack.getMin() # -2 约束 -2^31 <= value <= 2^31 - 1 最多调用 3 * 10^4 次 push、pop、top 和 getMin pop、top 和 getMin 调用时栈一定非空 Step 1：弹出最小值后，前一个最小值从哪里回来 普通栈已经能保存值，并按照后进先出的顺序执行 push、pop 和 top。当前 baseline 是： ...

题目要求 给定一个只包含以下六种字符的字符串 s： ( ) { } [ ] 判断这个字符串是否有效。有效字符串必须同时满足三个条件： 每个左括号都由相同类型的右括号闭合。 左括号必须按照正确顺序闭合。 每个右括号都有一个对应的同类型左括号。 满足全部条件时返回 True，否则返回 False。 示例 输入 输出 "()" True "()[]{}" True "(]" False "([])" True "([)]" False 约束 1 <= s.length <= 10^4 s 只包含 ()[]{} 中的字符 LeetCode 提供的方法签名是： class Solution: def isValid(self, s: str) -> bool: pass Step 1：数量相同为什么仍然无效 先看两个字符串： ()[]{} ([)] 它们都有一个 ( 和一个 )、一个 [ 和一个 ]。如果只分别统计三种左括号和右括号的数量，这两个字符串都会通过检查。 当前 baseline 是： 分别统计每种左括号和右括号；数量全部相同就认为字符串有效。 这个 baseline 会在 ([)] 上给出错误答案。问题不在括号数量，而在闭合顺序：读到一个右括号时，它必须闭合最近遇到、但还没有被闭合的左括号。 把这个规则用于 ([)]： ...

题目要求 给定一个编码字符串 s，返回它解码后的字符串。 编码规则是： k[encoded_string] 方括号中的 encoded_string 需要连续重复 k 次，其中 k 是正整数。编码可以嵌套，也可以与普通小写字母相邻。 题目保证： 输入字符串始终有效，方括号完整配对且没有多余空格。 原始文本不包含数字，数字只表示重复次数。 不会出现 3a 或 2[4] 这类不符合编码规则的输入。 解码后的字符串长度不会超过 10^5。 示例 输入 输出 "3[a]2[bc]" "aaabcbc" "3[a2[c]]" "accaccacc" "2[abc]3[cd]ef" "abcabccdcdcdef" 约束 1 <= s.length <= 30 s 只包含小写英文字母、数字和 [] 所有重复次数都在 [1, 300] 范围内 LeetCode 提供的方法签名是： class Solution: def decodeString(self, s: str) -> str: pass Step 1：进入内层以后，外层信息去了哪里 先从没有嵌套的输入开始： 3[a] 读到 3 后知道下一段需要重复三次；读完方括号中的 a，得到： a * 3 = aaa 当前 baseline 是： 读出一个重复次数，再收集后续方括号中的文本，遇到 ] 时执行重复。 这个 baseline 可以处理一层 3[a]，却会在 3[a2[c]] 上中断。外层已经读到重复次数 3 和普通字母 a，此时又遇到了内层编码 2[c]。如果直接把当前次数改成 2、当前文本改成 c，外层的 3 和 a 就丢失了。 ...

题目要求 给定一个非负整数数组 heights。每个 heights[i] 表示宽度为 1 的柱子高度，所有柱子紧挨排列。 题目要求返回柱状图中能够形成的最大矩形面积。 一个合法矩形必须覆盖一段连续柱子。它的宽度是这段区间包含的柱子数量，高度不能超过区间中的最矮柱。 LeetCode 提供的方法接口是： largestRectangleArea(heights: List[int]) -> int 示例 1 输入：heights = [2,1,5,6,2,3] 输出：10 下标 2 和 3 的两根柱子高度分别是 5 和 6，可以形成高度 5、宽度 2、面积 10 的矩形。 示例 2 输入：heights = [2,4] 输出：4 可以选择高度 4、宽度 1，也可以选择高度 2、宽度 2，最大面积都是 4。 约束 1 <= heights.length <= 10^5 0 <= heights[i] <= 10^4 Step 1：矩形面积不是柱高之和 先看一个小柱状图： heights = [2,1,2] 如果矩形覆盖全部三根柱子，它的宽度是 3，但高度最多只能是 1： height = 1 width = 3 area = 1 * 3 = 3 不能把三根柱高相加得到 5。柱状图矩形覆盖的是一块完整矩形区域，中间高度为 1 的柱子会限制整个区间的矩形高度。 ...

题目要求 给定一个整数数组 temperatures，其中 temperatures[i] 表示第 i 天的温度。 返回数组 answer，其中： answer[i] = 从第 i 天开始，需要等待多少天才会遇到更高温度 如果之后没有更高温度，answer[i] = 0。 这里的“更高”是严格大于。相同温度不能结算等待中的日期。 LeetCode 提供的方法接口是： dailyTemperatures(temperatures: List[int]) -> List[int] 示例 输入：temperatures = [73,74,75,71,69,72,76,73] 输出：[1,1,4,2,1,1,0,0] 约束 1 <= temperatures.length <= 10^5 30 <= temperatures[i] <= 100 Step 1：答案不是更高温度，而是等待天数 先看一个更小的输入： temperatures = [73,71,72,76] 逐天回答： 第 0 天是 73，右侧第一个更高温度是第 3 天的 76，等待 3 天。 第 1 天是 71，第 2 天的 72 更高，等待 1 天。 第 2 天是 72，第 3 天的 76 更高，等待 1 天。 第 3 天右侧没有日期，答案是 0。 所以结果是： ...

副标题 / 摘要 LeetCode 230 的难点不是“会中序遍历”，而是把 BST 的有序性用成真正有用的信息。只要抓住“中序第 k 次访问到的节点就是答案”，整题就会变成一个非常稳定的计数问题。 预计阅读时长：11~14 分钟 标签：Hot100、二叉树、BST、中序遍历、栈 SEO 关键词：Kth Smallest Element in a BST, 二叉搜索树中第 K 小的元素, BST, 中序遍历, 显式栈, LeetCode 230 元描述：系统讲透 LeetCode 230 的 BST 中序有序性、显式栈计数与提前停止技巧，并给出工程迁移与多语言实现。 A — Algorithm（题目与算法） 题目还原 给定一棵二叉搜索树 root 和一个整数 k，请找出这棵树中第 k 小的元素。 这里的 k 从 1 开始计数。 输入输出 名称 类型 描述 root TreeNode 二叉搜索树根节点 k int 第几个最小元素，1 <= k <= n 返回值 int 第 k 小的节点值 示例 1 输入：root = [3,1,4,null,2], k = 1 输出：1 示例 2 输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3 提示 树中的节点数为 n 1 <= k <= n <= 10^4 0 <= Node.val <= 10^4 进阶 如果 BST 经常插入、删除，并且需要频繁查询第 k 小，你会怎么优化？ ...

副标题 / 摘要 二叉树遍历是树题模板的起点，中序遍历则是“递归思维”和“显式栈模拟”最典型的一题。本文按 ACERS 结构拆解 LeetCode 94，把左-根-右的访问顺序、迭代栈写法和工程迁移价值一次讲清。 预计阅读时长：10~12 分钟 标签：Hot100、二叉树、DFS、栈、中序遍历 SEO 关键词：Hot100, Binary Tree Inorder Traversal, 二叉树的中序遍历, 中序遍历, 显式栈, LeetCode 94 元描述：从递归到显式栈，系统讲透 LeetCode 94 二叉树中序遍历，并给出工程场景迁移与多语言实现。 目标读者 正在刷 Hot100，希望把树遍历模板固定下来的同学 刚从数组 / 链表过渡到树结构，容易把前序、中序、后序顺序写混的开发者 需要在 BST、表达式树、抽象语法树里复用“左-根-右”思想的工程师 背景 / 动机 中序遍历本身不复杂，但它的训练价值很高： 它是“递归 = 隐式栈，迭代 = 显式栈”最容易建立直觉的一题 它能帮助你稳定掌握“先一路向左，再回退访问根，再转向右子树”的过程 在 二叉搜索树（BST） 里，中序遍历天然得到有序序列，工程迁移价值很强 很多人第一次写树题不是逻辑不会，而是： 不清楚访问顺序到底是谁先谁后 迭代版不知道什么时候入栈、什么时候出栈 一旦树为空或只有单边链，代码就容易写乱 这题把模板练熟，后面的验证 BST、找第 k 小元素、恢复二叉搜索树等题会更顺。 核心概念 中序遍历：按照 左子树 -> 根节点 -> 右子树 的顺序访问 DFS（深度优先搜索）：树遍历最常见的组织方式，中序遍历就是 DFS 的一种访问顺序 显式栈：把递归调用栈手动写出来，用栈保存“回头还要处理的节点” 树高 h：空间复杂度通常写成 O(h)，平衡树约为 O(log n)，极端退化链表时是 O(n) A — Algorithm（题目与算法） 题目还原 给定二叉树根节点 root，返回它的 中序遍历 结果。 ...

副标题 / 摘要 只有队列（FIFO）时，也能实现栈（LIFO）。本文展示单队列旋转法，并分析复杂度与边界。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 初中级算法学习者 背景 / 动机 栈的后进先出与队列的先进先出相反。 “旋转队列”可以把最新元素移动到队头，从而模拟栈顶。 核心概念 队列（FIFO）：先进先出 栈（LIFO）：后进先出 队列旋转：把新元素转到队首 实践指南 / 步骤 入栈：将元素入队 旋转队列：把队首依次出队再入队，直到新元素位于队首 出栈：直接出队 取栈顶：查看队首 可运行示例 from collections import deque class MyStack: def __init__(self): self.q = deque() def push(self, x: int) -> None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) -> int: return self.q.popleft() def top(self) -> int: return self.q[0] def empty(self) -> bool: return not self.q if __name__ == "__main__": s = MyStack() s.push(1) s.push(2) print(s.top()) print(s.pop()) print(s.empty()) 解释与原理 每次 push 后旋转队列，使新元素位于队首。 这样 pop 就相当于弹出“栈顶”。 ...

副标题 / 摘要 当系统只提供栈（LIFO）时，如何构建队列（FIFO）？本文用双栈法给出清晰实现与工程要点。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 希望掌握复杂度分析的初中级工程师 背景 / 动机 队列的先进先出与栈的后进先出相反。 双栈法通过“翻转顺序”实现队列语义，是经典的结构变换题。 核心概念 栈（LIFO）：后进先出 队列（FIFO）：先进先出 双栈翻转：把输入顺序倒置为输出顺序 实践指南 / 步骤 入队：压入 in 栈 出队/取队首：若 out 栈为空，将 in 栈全部弹出并压入 out 栈 从 out 栈弹出：即为队首 保持延迟搬运：只在 out 为空时搬运 可运行示例 class MyQueue: def __init__(self): self._in = [] self._out = [] def push(self, x: int) -> None: self._in.append(x) def _move(self) -> None: if not self._out: while self._in: self._out.append(self._in.pop()) def pop(self) -> int: self._move() return self._out.pop() def peek(self) -> int: self._move() return self._out[-1] def empty(self) -> bool: return not self._in and not self._out if __name__ == "__main__": q = MyQueue() q.push(1) q.push(2) print(q.peek()) print(q.pop()) print(q.empty()) 解释与原理 in 栈负责“输入顺序”，out 栈负责“输出顺序”。 当 out 为空时，把 in 全部倒入 out，就实现了 FIFO 的逆序输出。 ...

副标题 / 摘要 栈溢出通常由无限递归或过深调用导致。本文用可运行示例解释原因与规避策略。 目标读者 学习递归与算法的开发者 关注性能与稳定性的工程师 需要理解运行时限制的初学者 背景 / 动机 每次函数调用都会占用栈空间。 当调用深度超过上限，程序会抛出栈溢出错误或崩溃。 核心概念 调用栈：保存函数调用上下文 递归深度：递归层数过深会耗尽栈 尾递归优化：某些语言可复用栈帧 实践指南 / 步骤 确保递归有明确终止条件 控制递归深度或改为迭代 对深度递归设定保护阈值 在高风险路径做测试 可运行示例 import sys sys.setrecursionlimit(1000) def boom(n): return boom(n + 1) if __name__ == "__main__": try: boom(0) except RecursionError as e: print("stack overflow:", e) 解释与原理 每次递归都会压入新的栈帧。 当深度超过解释器或系统限制时，就会触发栈溢出。 常见问题与注意事项 提高递归深度就能解决吗？ 只能延迟问题，不能根治。 尾递归一定不会溢出吗？ 取决于语言是否支持尾递归优化。 迭代一定更好吗？ 不一定，但在深度很大时更安全。 最佳实践与建议 用迭代替代深度递归 为递归函数加入深度保护 对递归路径做压力测试 小结 / 结论 栈溢出是递归深度过大导致的运行时问题。 通过终止条件、迭代替换与深度限制可以有效避免。 参考与延伸阅读 Python Recursion Limit The Art of Computer Programming 元信息 阅读时长：5~7 分钟 标签：递归、栈溢出 SEO 关键词：栈溢出, 递归深度 元描述：解释栈溢出的成因与规避方式。 行动号召（CTA） 检查你的递归函数，确认终止条件是否足够严格。