Stack&Queue&Heap

发表于： 分类于：
字数： 3121 阅读：≈ 7分钟

灵神题单

合法括号字符串

32 最长有效括号

“()(())”

用一个数组tmp记录匹配成功的index。遇到(时，把它的 index 加入栈。遇到）时，从栈里pop出一个(，它们两个匹配成功，于是把tmp中它们两个的index上都标记为1.

最后统计最长的连续1子数组长度即可。

856. 括号的分数🌟

() 得 1 分。 AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分，其中 A 是平衡括号字符串。

比如()(())(),初始化stack=[0], res=0

每次见到(，往 stack 里面 push res, 表示存储之前的计算结果。另外要把res清零，接下来要开始用 res计算该括号内的值了。

每次见到), 需要计算它和它对应的左括号这一串的值大小，要么是1，要么是2*res值，则可以得到一个新的res；pop掉对应的左括号，则可以得到这对括号之前的值，所以res+=stack.pop()。如果此时结尾了，会返回res, 如果后面还有(,那么res会被放到栈里去。

1111. 有效括号的嵌套深度

思路一：(相当于加深度，)相当于降深度。每次遇到(时，把它分给深度较低的那个组，用 a, b分别记录两个组的深度。

思路二： 把嵌套深度为奇数的括号，和嵌套深度为偶数的括号，分别分到两个组。

邻项消除

1717. 删除子字符串的最大得分

贪心，先尽量删分值大的 ab, 再删分值小的 ba. 不需要用 while，因为消除之后两个字母都没了，所以一边 append 一边 pop 即可

735. 小行星碰撞

需要用 while， 因为有时候碰撞过后，新的小行星会留下来，继续和栈里的行星碰撞。

如果条件分支复杂，就加一个 flag。

表达式解析

394. decode string

输入：s = “3[a]2[bc]” 输出：“aaabcbc”
遇到[, 入栈，清空res和 multi
遇到]，出栈
res和 multi用来记录当前字符串的前缀，以及当前字符串需要重复的倍数。
记住 multi也有可能是100。

224. 基本计算器🌟

-2+(3-1)+4

用栈来处理括号

变量：res, num, sign, stack

初始+号（sign=1）很重要！

  1. 先考虑不带括号的情况，比如10+2-1
  • 遇见数字，更新 num
  • 遇见 ops，此时可以确定前面的 num了，更新res， 再更新 sign，把 num置0
  1. 再考虑带括号的情况，比如 1+(3-2)
  • 当遇到左括号的时候，需要保存此前的res和sign，把它们入栈；并置sign为 1，清空res
  • 遇到右括号，计算出这一块的res，然后从栈里取出之前的 res和sign,得到最终结果

772. 基本计算器 III🌟

s = “2*(5+5*2)/3+(6/2+8)”

用递归来处理括号

左括号：调用递归得到一个num, 消费掉后面的完整（expression） 右括号：在递归内部被 pop，此时 return res

单调栈

找左/右边第一个更大的数：降序栈

找左/右边第一个更小的数：升序栈

遍历方向：双向都可以，一种是去除无用，一种是去除已经有答案的数。

去除已经有答案的数：在循环里，一边把它弹出来，一边给它答案.
去除无用：在新遍历到某个数的时候，给它答案。

找右边第一个更大/小的数：从左到右遍历是去除已经有答案的数，从右到左是去除无用

想要留下那些最大的数：降序栈

739. 每日温度

  1. 从右往左遍历，此时发现5比2，3大，因此可以去除2和3。降序栈。已经不会是别人答案的数，不需要放在栈里。 Alt text
  2. 从左往右遍历，降序栈。已经拥有答案的数，不需要放在栈里。

LC 155 最小栈

84. Largest Rectangle in Histogram

需要前后两个哨兵节点[0]。找左右第一个更小的元素 用升序栈。当栈顶从栈里 pop 出来的时候，更新的答案高为heights[栈顶],width（这个矩形的左右边界）为此时的栈顶和i.

1124. 表现良好的最长时间段

找最远的l, r，使得s[r]>s[l]。这题是求最长，和其他单调栈模版不一样，需要两次遍历。

85.最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

思路：前缀和+栈。为每一行，计算该列的前缀和。问题转化为：对每一行算出来的前缀和，考虑最大矩形面积（单调栈）

问题转化：矩阵的高肯定是数组中的某个数字，所以枚举高度。
当枚举到数组中某个数字X的时候，考虑它的最大宽度是多少，也就是找该数字左，右边第一个比它小的位置

单调栈-字典序/数字最大

316. 去除重复字母

栈里面需要单调递增。

输入：s = “bcabc” 输出：“abc”

402. 移掉 K 位数字

需要注意细节处理

1944. 队列中可以看到的人数

去除无用。更新答案的逻辑需要仔细思考。

单调双端队列

239. 滑动窗口最大值 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res=[]
        dq=collections.deque()
        for i, x in enumerate(nums):
            if dq and dq[0]<i-k+1:
                dq.popleft()
            while dq and nums[dq[-1]]<=x:
                dq.pop()
            dq.append(i)
            if i>=k-1:
                res.append(nums[dq[0]])
        return res

LCR 184对应LC 155(min stack)

括号相关题

1963. 使字符串平衡的最小交换次数（贪心）

遇到左括号cnt+1, 遇到右括号cnt-1。不能使 cnt为负数，因此当cnt为 0，遇到右括号时，把它和左括号交换，此时操作数加一。

为了使总操作数最小，每次尽量与最右边的左括号交换，这样可以保证cnt-1 尽量到后面才执行。

单调栈变形

962. 最大宽度坡

给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。

  1. 考虑什么数可以留下来：越大的数可以越在左边当做 i
  2. 从右往左枚举j, 比较 num[stack[-1]]与num[j]的大小，一直 pop 到num[stack[-1]]>nums[j]，此时往左移动 j

把数组变为零

考虑相邻数字的大小关系

3542. 将所有元素变为 0 的最少操作次数🌟

在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。 返回使整个数组变为 0 所需的最少操作次数。

如果一个数，它左右两边的数字都比它小，那么它一定需要耗费一次，变为零

比它小->升序栈，一遇到降序，就把栈顶弹出去，代表它需要被单独处理。

12543

1526. 形成目标数组的子数组最少增加次数（差分数组）

在 全0数组 中选择 任意 子数组，并将子数组中每个元素增加 1 。

target = [1,2,3,2,1]

考虑[1,2],需要两步；[1,2,1]也需要两步。
所以观察升序，只要看到升序，就增加答案。

3229. 使数组等于目标数组所需的最少操作次数

在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。返回最少操作次数。

d=[1,−3,4]
为使得操作次数最少，每一次操作最好作用于一个正数和一个负数。

假设差分数组中，正数之和为 M，负数之和为 N ，假设 M>abs(N)，那么先操作 abs(N)次，再操作 M+N 次。则总操作次数为-N+M+N+M

所以最少操作次数为 max(M, abs(N))

队列设计

232. 用栈实现队列🌟

一个栈作为输入栈，另一个栈作为输出栈

622. 设计循环队列

用长度为(capacity+1)的数组实现，用 rear 指向下一个数放置的 index，front 指向当前队列第一个元素的 index。

判断队列为满：rear 的下一个index 正好指向 front

1

(self.rear+1)%(self.k+1)==self.front

判断队列为空：

1

self.front==self.rear

单调队列

1438. 绝对差不超过限制的最长连续子数组🌟

两个双端队列，队首分别是当前窗口的最大值和最小值

不能合并重复元素！！！不然会导致本应存在的值被提前移除

Heap

前 K 大，前 K 小 或者 第 K 个， K 个最 Problem: 347. 前 K 个高频元素

Problem: 215. 数组中的第K个最大元素

Problem: 703. 数据流中的第 K 大元素

Problem: 692. 前K个高频单词

Problem: 973. 最接近原点的 K 个点

Problem: 面试题 17.14. 最小K个数

1942. 最小未被占据椅子的编号🌟

注意遍历方法！

  1. 椅子释放的时间需要排序。用 releaseTime 这个 heap 来记录此时那些被占有的椅子和他们被释放的时间，和该椅子的序号。对于同一个时间点，先出再进。所以是遍历每个人
  2. 椅子序号需要排序。用 seats 这个 heap来装所有被释放的椅子
1

times=sorted(zip(times, range(n)))

常用的排序方法，可以保留原始的 index

1882. 使用服务器处理任务

遍历方法：遍历任务，因为每个任务和时间是绑定的。
如果 serverQ 为空的话，则从 releaseQ 里面拿出一个最先被释放的 server 来，执行现在的任务。现在的时间并不改变

2406. 将区间分为最少组数

按区间遍历的思想

1834. 单线程 CPU

另一种遍历的思想：自由控制时间

621. 任务调度器🌟

重排元素

1353. 最多可以参加的会议数目

按天遍历。

373. 查找和最小的 K 对数字

思考进堆出堆的逻辑关系