力扣刷题笔记 #11 栈&队列

本文包含「栈&队列」类型题中的：栈和队列模拟、括号配对、单调栈等。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

栈和队列模拟

946. 验证栈序列 (M)

题目描述：给定 pushed 和 popped 序列，当其可能是一个真实空栈上发生的序列时，返回 true。

方法：栈模拟，将 pushed 入栈，同时判断栈顶元素是否为 popped 序列当前指向的元素，如果是则连续出栈，如果不是则继续入栈。当 pushed 遍历完时，模拟的栈为空则代表真实可行。

坑点：取栈顶元素时如果栈为空则会发生数组越界错误！

895. 最大频率栈 (H)

题目描述：设计一个 FreqStack 类，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

方法：哈希表 + 多栈，用哈希表 \(freq\) 存储每个值出现的次数，记当前最大频率为 \(maxFreq\)，为每一种频率单独设置一个栈，所有栈用哈希表 \(ss\) 维护。所有操作的时间复杂度均为 \(O(1)\)。

• 每次出栈都发生在 \(maxFreq\) 对应的栈，当该栈为空时，自动转到下一个。
• 每次入栈都会将 \(val\) 加入其当前频率对应的栈，且不会删除之前栈中已有的 \(val\)。
• 如果有最大频率对应着多个数字，也能保证弹出的一定是最后入栈的元素。

Todo 用两个栈模拟队列 (M)

括号配对

20. 有效的括号 (E)

题目描述：给定一个只包含 (){}[] 的字符串，验证括号是否有效，不区分三种括号的优先级。

方法1：栈模拟，当遇到一种左括号时，将对应的右括号入栈；遇到一种右括号时，比对栈顶元素是否相等，相等则出栈。最后栈为空则有效，时间复杂度 \(O(n)\)。

方法2：栈模拟 + 哈希表，上述写法通常需要若干个条件判断语句，如果用哈希表存储 左括号->右括号 的映射就能减少代码的冗余，但在本题上不会显得更高效。

坑点：当字符串长度为奇数时，可以直接返回 false。

921. 使括号有效的最少添加 (M)

题目描述：给定一串括号序列，只有当括号正确配对时序列才是有效的，正确配对的括号包括 (()) 和 ()() 等。计算要使原括号序列有效而必须添加的最少括号数。

方法1：贪心 + 栈模拟，括号问题最容易想到的就是栈模拟法，当遇到左括号时入栈，遇到右括号时出栈匹配。如果遇到右括号时栈为空，则只能添加一个左括号进行匹配。最终答案是添加的左括号数和栈中剩余的左括号数，复杂度 \(O(n)\)。

方法2：贪心 + 计数，上一个方法中，栈中只会存放左括号，因此可以简化为一个变量来计数栈中的元素个数，空间复杂度降为 \(O(1)\)。

856. 括号的分数 (M)

题目描述：给定一串平衡括号序列（正确匹配），按下列规则计算字符串的分数：() 得 1 分，AB 得 A + B 分，(A) 得 2A 分，其中 A 和 B 都是平衡括号序列。

方法1：前缀和 + 分治，对原串进行分解，如果是 AB 则递归处理两边，如果是 (A) 则去掉最外层括号处理内层。时间复杂度为 \(O(n^2)\)，空间复杂度为递归深度 \(O(n)\)。

如何判断该分为哪种？将左括号记为 \(1\)，右括号记为 \(-1\)，累积前缀和，当前缀和为 \(0\) 时，说明前缀就是一个平衡括号序列，可以分治。这种方法的前提是括号要正确匹配！

方法2：栈模拟，栈中无需记录括号类型（只会存放左括号），只需记录当前分数。遇到左括号时入栈分数 0，遇到右括号时，弹出栈顶元素，计算新分数并累加到下一个栈顶元素。时空复杂度均为 \(O(n)\)。

方法3：计数，最终的分数只与 () 有关，其他情况只改变其所在深度而间接改变结果，当深度为 dep 时分数为 1<<dep。每次遇到左括号时当前深度加一，遇到右括号时深度减一。每次遇到右括号就更新一次答案，时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

394. 字符串解码 (M)

题目描述：给定形如 3[a2[b]] 的加密字符串，方括号内部的字符会重复前面的数字的次数，返回解码后的字符串。

方法1：栈模拟，当数字时处理完进栈，遇到字母或 [ 时直接进栈，遇到 ] 时将栈顶的字母或字符串全部弹出到 vec 并翻转 vec，并且此时 [ 的下一个元素一定是数字，将栈顶的字符串重复后再入栈，当遍历结束后栈中就是结果。时空复杂度均为 \(O(n)\)。

方法2：双栈，数字存放在数字栈，字母存放在字母栈，遇到右括号时候弹出一个数字栈，字母栈弹到左括号为止。处理起来相对简单，其他步骤细节不变。

注意最后栈中元素的正确顺序应当从栈底到栈顶，所以可以用 vector 来模拟栈。此外，栈顶弹出时需要放到 vector，再翻转整个 vector，则是考虑到有些字符串已经翻转过了，而单字母还没翻转过。

方法3：递归，定义一个全局指针 \(now=0\)，递归结束条件是 \(now=n\) 或者遇到 ]；递归返回时由于可能会有多个平衡串，返回结果是 \(res+getSring()\)，继续向后递归。时空复杂度均为 \(O(n)\)，\(n\) 为解码后的串长。

如果遇到纯字母，则可以将连续的一串字母取出，继续递归下一个元素；

如果遇到数字，则处理出数字串后，下一个是 [，跳过并递归访问子串，子串结果保存在临时变量中，出递归后还要跳过 ]。最后将临时变量重复若干次，继续递归。

32. 最长有效括号 (H)

题目描述：给定只包含 ( 和 ) 的字符串，找出其中最长有效（正确匹配）连续子串的长度。

方法1：一维 DP，定义 \(dp[i]\) 表示以下标 \(i\) 为结尾的最长有效括号长度，有效的子串一定以 ) 结尾，由于子串要求连续，\(dp[i]\) 与 \(s[i-1]\) 的取值有关。时空复杂度均为 \(O(n)\) 。

如果 \(s[i-1]\) 取 (，则恰好与 \(s[i]\) 配对，状态转移方程为： \[ dp\left[ i \right] =dp\left[ i-2 \right] +2 \] 如果 \(s[i-1]\) 取 )，则 \(dp[i-1]\) 可能是一个非零值，代表 \(s[i-dp[i-1]]\) 到 \(s[i-1]\) 是一个有效的子串，则如果 \(s[i-dp[i-1]-1]\) 取 (，就能和当前的 \(s[i]\) 配对。考虑到配对后的子串还会向前延伸，状态转移方程如下： \[ dp\left[ i \right] =dp\left[ i-1 \right] +dp\left[ i-dp\left[ i-1 \right] -2 \right] +2 \]

方法2：栈模拟，遇到 ( 时将下标入栈，遇到 ) 时弹出栈顶元素，此时「当前下标 - 下一个栈顶元素」就是以当前下标为结尾的最长有效括号长度。如果栈为空，则说明当前的 ) 不可能匹配成功，将其入栈作为分界点。由此可以推断一开始时应该将 -1 入栈，表示最左分界点。时空复杂度均为 \(O(n)\)。

该方法巧妙之处在于，同一个栈顶元素可能被多次访问，而中间已经配对的子串会自动被考虑，类似 DP 向前延申。

方法3：贪心 + 计数，分别记录左右括号的个数，当 \(right\) 计数器比 \(left\) 计数器大时，必不可能匹配，二者同时清零；当二者相等时，答案就是二者之和，且不需要清零。只正向遍历会漏掉 (() 的情况，因此需要再反向遍历，时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

表达式配对

单调栈

针对 下/上 一个更 大/小 值问题，正/反 向遍历数组，用一个单调递 增/减 的栈存储可能值，将不可能的值提前出栈，就可以把复杂度优化到 \(O(n)\)。基本模板如下：

// 正向遍历，单调递增栈，left[i] 存放左边第一个小于 nums[i] 的数
for(int i = 0; i < n; i++){
    while(!s.empty() && s.top() >= nums[i]) s.pop(); // 这里的符号与要求的相反
    if(s.empty()) left[i] = -1; // 可以通过初始化省掉这句
    else left[i] = s.top();
    s.push(nums[i]);
}

此外，单调栈还可以「反用」，不仅可以为「新入栈的元素」找到目标值，还可以为「出栈的元素」找到另一个方向遍历的反目标值：

// 正向遍历，left[i] 存放左边第一个小于 nums[i] 的数
// right[s.top()] 存放右边第一个小于等于 nums[s.top()] 的数
for(int i = 0; i < n; i++){
    while(!s.empty() && nums[s.top()] >= nums[i]){
        right[s.top()] = i; 
        s.pop();
    }
    if(!s.empty()) left[i] = s.top();
    s.push(i); // 此时 left right 还有 s 中都存放的是下标
}

739. 每日温度 (M)

题目描述：给一个温度数组，求对于每一天，下一个更高温度出现在几天后，如果没有更高温度则返回零。

方法1：暴力，两层循环，内循环正向遍历直到找到下一个更大元素，复杂度 \(O(n^2)\)。

方法2：单调递减栈，正向遍历数组，每一个新元素都会弹出栈顶比它小的所有元素（因为其存在会阻断右边所有元素被选中的可能），所有弹出元素都得到答案。然后将新元素入栈。时空复杂度均为 \(O(n)\)。

907. 子数组的最小值之和 (M)

题目描述：给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个连续子数组。

方法1：两个单调栈 + 乘法原理，用两个单调递增栈预处理得到 \(arr[i]\) 左边第一个 \(<arr[i]\) 的下标，右边第一个 \(\leqslant arr[i]\) 的下标，得到左开右闭区间，两边相乘计算贡献。时空复杂度均为 \(O(n)\)。

方法2：正反单调栈，在第一个栈预处理左边界时，栈顶元素 \(\geqslant arr[i]\) 需要 pop，此时 \(i\) 恰好是栈顶元素的右边界，可以一起标记。时空复杂度均为 \(O(n)\)。

方法3：进一步地，由于栈顶下面的元素正好也是栈顶元素的左边界，所以甚至连 \(left\) 和 \(right\) 数组都不需要，直接在出栈的时候计算贡献，为简化代码逻辑，可以在遍历前在 \(arr\) 末尾和栈顶分别加一个 \(−1\)，当作哨兵。空间复杂度 \(O(1)\)。

42. 接雨水 (H)

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

方法1：暴力，对于每个坐标，其能接的水量取决于左右两边最高的柱子中较矮者，两层循环遍历，复杂度 \(O(n^2)\)。

方法2：DP 预处理最大值，两次扫描，记录每个柱子的左右两边最大值，再扫描累计，时空复杂度均为 \(O(n)\)。该方法可以简单优化：从左到右的预处理可以和第三次扫描合并，用一个变量存储左边最大值，节省一个数组。

方法3：单调栈 + 模拟，每遍历到一个柱子，如果比栈顶元素更小则入栈，如果更大则说明前面的柱子可以形成水洼，则依次将所有较小数弹出，并计算和新柱子的差值，再把新柱子入栈。时空复杂度均为 \(O(n)\)。

方法4：贪心 + 对撞双指针，双指针从两端开始遍历，再用两个变量存储左右两边最大值，每次较小者向中间收窄一格，同时计算出当前柱子能接的水量。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

方法5：分治 + 面积法，最高柱子将全局分为两边，两边各有各自的次高柱子，次高柱子与最高柱子中间的区域显然取值就是「次高柱子 - 当前柱子」，同理以此类推到两端。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。具体计算方法参考 力扣刷题笔记 #1 数组。

坑点：最左边、最右边两个柱子不可能接到水，要跳过，本题的所有方法可以直接从 1 遍历到 n-2。

84. 柱状图中最大的矩形 (H)

题目描述：给定非负整数数组，表示柱状图中各个柱子的高度。柱子彼此相邻且宽度为 \(1\)，求图中最大矩形的面积。

方法1：暴力枚举宽度，用两层循环表示左、右边界，在内层循环维护区间内最大值，求出面积，时间复杂度 \(O(n^2)\)。

方法2：暴力枚举高度，枚举每个柱子作为最低高度，找出两侧第一个小于该柱子的位置作为边界，时间复杂度 \(O(n^2)\)。

方法3：正反单调栈，改进方法 2，用单调栈预处理两侧第一个小于的位置，时空复杂度均为 \(O(n)\)。

85. 最大矩形 (H)

题目描述：给定一个仅包含 0 和 1 的 \(m\times n\) 二维矩阵，找出只包含 1 的最大矩形，并返回其面积。

方法1：暴力枚举 + 前缀和，枚举矩形的左上角和右下角，并判断矩形内是否全为 1（区间和等于矩形大小），复杂度 \(O(m^2n^2)\)。

方法2：转化成柱状图，预处理出矩阵每个位置的上方有多少个连续的 1，再取出每一行，将该行视为柱状图，计算图中最大矩形的面积，时间复杂度 \(O(mn^2)\)。

方法3：柱状图 + 单调栈优化，时间复杂度 \(O(mn)\)。

2453. 下一个更大元素 IV (H)

题目描述：给定数组 nums，求其中每个元素的下下个更大元素（两个数都大于 \(nums[i]\)，不需要递增）。

方法1：两个反单调栈，正向遍历，栈 \(s\) 存放第一轮，栈 \(t\) 存放第二轮，都是单调递减栈，每次出栈代表找到下一个更大元素。每遍历到一个新元素先将 \(t\) 中的数较小数弹出（这些弹出的元素都得到答案），再将新元素放入 \(s\) 中，\(s\) 弹出的元素按照原顺序放入 \(t\)。时间复杂度 \(O(n)\)。

不能用正向单调栈的原因：在栈 \(s\) 中找到下一个更大元素后，下下个更大元素可能在 \(s\) 栈剩余元素中，也可能在 \(t\) 栈中。而使用反向单调栈，元素每次出栈都代表找到了下一个更大元素。

这题的巧妙之处在于：每新来一个 \(x\)，第一个 while 使得 \(t\) 中没有比 \(x\) 小的数，所以可以让 \(s\) 中比 \(x\) 小的数直接加在 \(t\) 后面，同时维持 \(t\) 单调递减。而 \(s\) 又是递减的，所以第二个 while 直接截取小于 \(x\) 的后缀，不改变顺序就能接在 \(t\) 后面。

方法2：反单调栈 + 优先队列，反单调栈用法同上，优先队列存放栈弹出的元素（已经找到了第一个更大元素的），每遍历到一个新元素，如果这个数比队首元素大，则队首元素就得到答案。该方法实现比较简单，时间复杂度 \(O(n\log n)\)。