栈与队列相关的问题就比较微妙了，很多时候相关题目中压根不会出现“栈”、“队列”这样的关键字，但只要你深入到真题里去、对栈和队列的应用场景建立起正确的感知，那么很多线索都会在分析的过程中被你轻松地挖掘出来。
这里也和大家分享一位读者在试读过程中的学习感悟：
感觉算法题除了理解还要靠练习，就像高考数学题，要锻炼出解题常规思维。任重道远啊🙊
其实就是这么回事，这也正是我们开篇就跟大家指明“以题为纲”这条路的初衷。
好啦，开工了老哥们！
# 典型真题快速上手-“有效括号”问题
30 秒速记
- 括号嵌套 = 最后打开的最先关闭 = 栈的后进先出
- 遇到左括号，把「期待的右括号」压栈；遇到右括号，和栈顶比
- 栈空时来了右括号、或者和栈顶对不上 → 立刻
false - 扫完还要
stack.length === 0，不然((会被判对 - 时间
O(n)，最坏空间O(n)；奇数长度可以直接false
看到括号匹配就想到栈：最后打开的括号必须最先关上，这正是后进先出。 我的写法是遇到左括号就把对应的右括号压进去，遇到右括号就弹出栈顶比一下，对不上或者栈已经空了就直接返回 false。扫完一遍还要检查栈是不是空的，剩下的就是没关上的左括号。
const pair = { '(': ')', '[': ']', '{': '}' }
function isValid(s) {
const stack = []
for (const ch of s) {
if (pair[ch]) stack.push(pair[ch])
else if (stack.pop() !== ch) return false
}
return stack.length === 0
}
isValid('([)]') // false
isValid('{[]}') // true
回答参考：“括号嵌套要求最后打开的括号最先关闭，正好符合 LIFO。我把期望的闭括号压栈，右括号只需和栈顶比较。”
题目描述：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
- 输入: “()”
- 输出: true
示例 2:
- 输入: “()[]{}”
- 输出: true
示例 3:
- 输入: “(]”
- 输出: false
示例 4:
- 输入: “([)]”
- 输出: false
示例 5:
- 输入: “{[]}”
- 输出: true
思路分析
括号问题在面试中出现频率非常高， 这类题目我们一般首选用栈来做。
为什么可以用栈做？大家想想，括号成立意味着什么？意味着对称性。
巧了，根据栈的后进先出原则，一组数据的入栈和出栈顺序刚好是对称的。比如说1、2、3、4、5、6按顺序入栈，其对应的出栈序列就是 6、5、4、3、2、1：
123456
654321
对称关系一目了然。
因此这里大家可以记下一个规律：题目中若涉及括号问题，则很有可能和栈相关。
回到题目中来，我们的思路就是在遍历字符串的过程中，往栈里 push 括号对应的配对字符。比如如果遍历到了 (，就往栈里 push )。
假如字符串中所有的括号都成立，那么前期我们 push 进去的一定全都是左括号、后期 push 进去的一定全都是右括号。而且左括号的入栈顺序，和其对应的右括号的入栈顺序应该是相反的，比如这个例子：
({[]})
最后一个入栈的左方括号[，与之匹配的右方括号]正是接下来第一个入栈的右括号。
因此，我们可以果断地认为在左括号全部入栈结束时，栈顶的那个左括号，就是第一个需要被配对的左括号。此时我们需要判断的是接下来入栈的第一个右括号是否和此时栈顶的左括号配对。如果配对成功，那么这一对括号就是有效的，否则直接 return false。
当判断出一对有效的括号之后，我们需要及时地丢掉它，去判断其它括号是否有效。这里这个“丢掉”的动作，就对应着两个括号一起出栈的过程。
每配对成功一对括号，我们都将这对括号出栈。这样一来，我们就可以确保栈顶的括号总是下一个需要被匹配的左括号。
如果说我们出栈到最后，栈不为空，那么意味着一部分没有被匹配上的括号被剩下来了，说明字符串中并非所有的括号都有效，判断 false；反之，则说明所有的括号都配对成功了，判断为 true。
编码实现
// 用一个 map 来维护左括号和右括号的对应关系
const leftToRight = {
"(": ")",
"[": "]",
"{": "}"
};
/**
* @param {string} s
* @return {boolean}
*/
const isValid = function(s) {
// 结合题意，空字符串无条件判断为 true
if (!s) {
return true;
}
// 初始化 stack 数组
const stack = [];
// 缓存字符串长度
const len = s.length;
// 遍历字符串
for (let i = 0; i < len; i++) {
// 缓存单个字符
const ch = s[i];
// 判断是否是左括号，这里我为了实现加速，没有用数组的 includes 方法，直接手写判断逻辑
if (ch === "(" || ch === "{" || ch === "[") stack.push(leftToRight[ch]);
// 若不是左括号，则必须是和栈顶的左括号相配对的右括号
else {
// 若栈不为空，且栈顶的左括号没有和当前字符匹配上，那么判为无效
if (!stack.length || stack.pop() !== ch) {
return false;
}
}
}
// 若所有的括号都能配对成功，那么最后栈应该是空的
return !stack.length;
};
面试官追问
追问 1只统计三种括号的左右数量相等，([)] 能判对吗？
判不对，它数量是相等的。数量只说明没缺，说明不了顺序。扫到 ) 时栈顶期待的是 ]，栈的写法当场就返回 false。
追问 2单个 ] 被判成合法，{[] 也通过了，查哪两处？
] 通过说明右括号来时没处理空栈，空栈 pop() 返回 undefined，要当成不匹配。{[] 通过说明最后少了 stack.length === 0 的检查。
追问 3编辑器要标出第一个出错的位置，栈里存什么？
存左括号的下标，或者 { expect, index }。右括号不匹配就报当前下标；扫完栈里还有东西，就报剩下那些左括号的位置。
追问 4输入是一整段代码，比如 if (a[0]) {}，其他字符怎么办？
先定契约。纯括号题里出现别的字符就算非法；校验代码的场景就跳过非括号字符，只处理那六种。两种语义别混在一个函数里。
追问 5超长文本分块流式进来，还能用栈吗？
能。块和块之间把栈留着接着用，匹配逻辑不需要整串。只是最终结论要等流结束才能下，全是左括号的话栈还是会长到 O(n)。
# 栈问题进阶-每日温度问题
30 秒速记
- 这是「下一个更大元素」模板题，用单调栈
- 栈里存还没等到升温的下标，不是温度（要算天数差）
- 栈里温度从底到顶单调不增；新温度更高就用
while连续弹，结算i - top - 相等不弹，题目要「严格更高」
- 每个下标最多进出一次，
O(n)；结果数组预填0，没弹出的自然就是0
每日温度是典型的单调栈：栈里放还没等到更高温度的那些天的下标，新的一天比栈顶热，就把栈顶弹出来，两个下标一减就是等了几天。 暴力两层循环是 O(n²)，问题在于同一段温度被反复扫。用栈的话，一个温度一旦遇到比它高的就结算掉，再也不看，每个下标最多进出一次，O(n)。注意要用 while 连续弹，一个高温可能同时解决好几天。
const res = new Array(T.length).fill(0), stack = []
for (let i = 0; i < T.length; i++) {
while (stack.length && T[i] > T[stack.at(-1)]) {
const top = stack.pop()
res[top] = i - top
}
stack.push(i)
}
// [73,74,75,71,69,72,76,73] => [1,1,4,2,1,1,0,0]
回答参考：“这是 next greater element。我维护未结算下标的单调递减栈，新元素一旦更大，就成为被弹下标右侧第一个更大值。”
题目描述: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
思路分析
