langShiftlangShift

栈（题单顺序）

热题 100 - 栈分组（按题单顺序）：20 / 155 / 394 / 739 / 84

本页包含题单「栈」分组的全部题目，顺序与 list.json 保持一致。

栈题统一“思维抓手”（点击展开）
  • 栈适合解决“最近的/成对的/回退”的关系：最近的左括号、最近更大/更小元素、解析嵌套结构等。
  • 单调栈的核心不变量：栈内元素按值单调（递增或递减），被弹出的元素说明“它的答案已经确定”。
  • 下标 vs 值：多数数组类栈题（739/84）栈里存下标，因为需要算距离/宽度。

20. 有效的括号

力扣原题：20. 有效的括号
Easy
栈
字符串

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

 

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成
最优解（栈：遇到右括号就匹配最近的左括号）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
  • 括号合法的本质：必须“后开先关”。最近打开的括号一定要最先被关闭。
  • 这句“后开先关”就是典型的 栈 行为（LIFO）。
  • 推理流程：
    • 遇到左括号：先记下来，等后面来关它 → 入栈
    • 遇到右括号：必须和“最近的左括号”匹配 → 出栈并检查类型
  • 为什么最后还要栈空？：如果还有没关掉的左括号，字符串也不合法。
类似题目（括号/消消乐：栈匹配最近元素）
for ch in s:

  if opening: push

  else: pop and check

return stack empty

155. 最小栈

力扣原题：155. 最小栈
Medium
栈
设计

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

 

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

 

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次
最优解（双栈：数据栈 + 最小值栈）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
  • 难点：普通栈的 pop/top 都是 (O(1))，但 getMin 如果每次都扫描一遍栈，会变成 (O(n))。
  • 关键推理：把“历史最小值”也一起压栈：
    • 当我们 push 一个值 val，我们其实想知道“push 之后栈里的最小值是多少”。
    • 这个最小值 = min(之前的最小值, val)。
    • 所以用另一个栈 minSt，让 minSt[i] 记录“主栈 st 在高度 i 时的最小值”。
  • 为什么 pop 时两个栈都 pop？：因为它们是一一对应的，栈高度必须同步。
类似题目（栈增强：额外维护一个“前缀最值/前缀信息”栈）
push(x): minSt.push(min(minSt.top, x))

pop(): st.pop(); minSt.pop()

getMin(): minSt.top

394. 字符串解码

力扣原题：394. 字符串解码
Medium
栈
递归
字符串

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

 

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

 

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300] 
最优解（栈：遇到 ] 就把最近一段出栈展开）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
  • 题目结构像“嵌套盒子”：k[ ... ] 表示把括号里的内容重复 k 次，并且括号可以嵌套。
  • 为什么需要栈？：因为嵌套意味着你会“进入一层括号”，之后还要“回到上一层继续拼接”，这正是栈保存上下文的场景。
  • 我们需要保存什么上下文？
    • 进入 [ 前已经拼好的字符串 prev
    • 对应的重复次数 k
  • 推理执行过程：
    • 读数字：累积成 num（注意可能是多位数）
    • 读到 [：把 [prev, num] 入栈，然后开始构造新的 cur
    • 读到 ]：弹出 [prev, k]，把 cur.repeat(k) 接回 prev，成为新的 cur
  • 这样每遇到 ]，就完成最近一层的展开，天然符合“后开先关”。
类似题目（解析嵌套结构：栈保存上层状态）
on "[": push(currentState); reset

on "]": state = pop(); merge

739. 每日温度

力扣原题：739. 每日温度
Medium
栈
数组
单调栈

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

 

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

 

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100
最优解（单调栈：栈里保持“递减温度下标”）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
  • 题意翻译：对每一天，找下一次更高温度出现要等几天。
  • 朴素做法：对每个 i 往后扫，最坏 (O(n^2))。
  • 关键推理：用栈保存“还没找到更高温度的天”：
    • 栈里放下标，并保持对应温度 递减。
    • 当今天温度 T[i] 比栈顶那天温度更高时，说明栈顶那天终于等到了更热的一天，答案就是 i - j。
    • 继续弹栈，直到栈顶温度比今天更高（或栈空）。
  • 为什么要递减？：
    • 递减保证“栈顶是最容易被今天打败的那天”，一旦今天更热，就能连续解决一串天数。
    • 每个元素最多进栈一次、出栈一次，所以总复杂度 (O(n))。
类似题目（下一个更大元素：单调栈）
for i:

  while stack not empty and a[i] > a[stack.top]:

    ans[stack.top] = i - stack.top

    stack.pop()

  stack.push(i)

84. 柱状图中最大的矩形

力扣原题：84. 柱状图中最大的矩形
Hard
栈
数组
单调栈

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

 

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104
最优解（单调栈：每根柱子当“最矮”时的最大宽度）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
  • 朴素思路：枚举每个柱子往左右扩展找能延伸多宽，最坏 (O(n^2))。
  • 关键推理：最大矩形一定有一个“最矮柱子”决定高度：
    • 如果我们把某根柱子 mid 当作矩形的最矮高度，那么矩形能延伸的左右边界就是：
      • 左边第一个 < h[mid] 的位置
      • 右边第一个 < h[mid] 的位置
    • 宽度一旦确定，面积就是 h[mid] * width。
  • 怎么快速找到“左右第一个更矮”？用单调递增栈：
    • 栈里保持高度递增，这样当遇到更矮的柱子 h[i] 时，说明栈顶柱子的“右边界”就是 i。
    • 弹出栈顶 mid 后，新的栈顶 left 就是 mid 的左边界（第一个更矮）。
    • 宽度 = i - left - 1。
  • 为什么两端加 0？
    • 让所有柱子都能在某个时刻被弹出并计算面积，避免最后还要额外清栈的逻辑。
类似题目（单调栈求左右边界）
add sentinel 0 at both ends

maintain increasing stack

on drop: pop mid, left = stack.top, right = i

二分查找（题单顺序）

热题 100 - 二分查找分组（按题单顺序）：35 / 74 / 34 / 33 / 153 / 4

堆（题单顺序）

热题 100 - 堆分组（按题单顺序）：215 / 347 / 295