langShift栈（题单顺序）
热题 100 - 栈分组（按题单顺序）：20 / 155 / 394 / 739 / 84
本页包含题单「栈」分组的全部题目，顺序与 list.json 保持一致。
栈题统一“思维抓手”（点击展开）
- 栈适合解决“最近的/成对的/回退”的关系：最近的左括号、最近更大/更小元素、解析嵌套结构等。
- 单调栈的核心不变量：栈内元素按值单调（递增或递减），被弹出的元素说明“它的答案已经确定”。
- 下标 vs 值：多数数组类栈题（739/84）栈里存下标，因为需要算距离/宽度。
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
示例 5：
输入：s = "([)]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
最优解（栈：遇到右括号就匹配最近的左括号）
最优解讲解（通俗版 + 推理过程）
- 括号合法的本质：必须“后开先关”。最近打开的括号一定要最先被关闭。
- 这句“后开先关”就是典型的 栈 行为（LIFO）。
- 推理流程：
- 遇到左括号：先记下来，等后面来关它 → 入栈
- 遇到右括号：必须和“最近的左括号”匹配 → 出栈并检查类型
- 为什么最后还要栈空？：如果还有没关掉的左括号，字符串也不合法。
类似题目（括号/消消乐：栈匹配最近元素）
for ch in s:if opening: pushelse: pop and checkreturn stack empty
155. 最小栈
设计一个支持 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 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
最优解（双栈：数据栈 + 最小值栈）
最优解讲解（通俗版 + 推理过程）
- 难点：普通栈的
pop/top都是 (O(1))，但getMin如果每次都扫描一遍栈，会变成 (O(n))。 - 关键推理：把“历史最小值”也一起压栈：
- 当我们 push 一个值
val，我们其实想知道“push 之后栈里的最小值是多少”。 - 这个最小值 =
min(之前的最小值, val)。 - 所以用另一个栈
minSt，让minSt[i]记录“主栈 st 在高度 i 时的最小值”。
- 当我们 push 一个值
- 为什么 pop 时两个栈都 pop？：因为它们是一一对应的，栈高度必须同步。
类似题目（栈增强：额外维护一个“前缀最值/前缀信息”栈）
push(x): minSt.push(min(minSt.top, x))pop(): st.pop(); minSt.pop()getMin(): minSt.top
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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 <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
最优解（双栈：numStack 存倍数，strStack 存进入 [ 前的字符串）
最优解讲解（通俗版 + 推理过程）
这题其实是**「括号展开 + 倍数复制」**的小型解释器：遇到 k[xxx]，就把 xxx 展开后重复 k 次。例如：3[a2[c]] → accaccacc。难点只有一个：嵌套。
思路：用「栈」一层一层拆。从左到右扫字符串，当成在“实时翻译”。
两个栈：
| 栈 | 作用 |
|---|---|
| numStack | 存倍数 k |
| strStack | 存进入 [ 之前已经拼好的字符串 |
两个当前变量：
- curNum：正在读取的数字（可能是多位数，如
12[a]） - curStr：当前层正在构造的字符串
逐字符规则：
- 遇到数字：
curNum = curNum * 10 + 当前数字 - 遇到
[：进入新的一层。把当前状态存起来：numStack.push(curNum)、strStack.push(curStr)，然后重置curNum = 0、curStr = ""（像递归进入下一层括号）。 - 遇到字母：
curStr += 字母 - 遇到
]：当前层结束，结算。k = numStack.pop()，prevStr = strStack.pop()，curStr = prevStr + curStr.repeat(k)（子问题完成，回到上一层）。
示例：3[a2[c]]
| 读到 | 操作 | curStr | numStack | strStack |
|---|---|---|---|---|
| 3 | 记录数字 | "" | [3] | [""] |
| [ | 入栈 | "" | [3] | [""] |
| a | 拼接 | "a" | [3] | [""] |
| 2 | 记录数字 | "a" | [3] | [""] |
| [ | 入栈 | "" | [3,2] | ["","a"] |
| c | 拼接 | "c" | [3,2] | ["","a"] |
| ] | 出栈结算 | "acc" | [3] | [""] |
| ] | 出栈结算 | "accaccacc" | [] | [] |
为什么是最优解？ 每字符只遍历一次 → 时间 O(n)；栈空间最多为嵌套层数 → 空间 O(n)。不用递归，不爆栈，是面试里的标准写法。
一句话总结：用栈模拟递归，把每一层括号当成一段子串，遇到 ] 再回到上一层拼接。
类似题目（解析嵌套结构：栈保存上层状态）
- 遇到
[：入栈当前状态，重置当前层 - 遇到
]：出栈，用栈顶状态与当前结果合并
739. 每日温度
给定一个整数数组 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 <= 10530 <= 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.topstack.pop()stack.push(i)
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=1050 <= 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 endsmaintain increasing stackon drop: pop mid, left = stack.top, right = i