每日算法刷题Day60:8.10:leetcode 队列5道题，用时2h

三、双端队列

1.套路

1.反转就当做双端队列换一个方向处理

2.题目描述

1.你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。(答案)

3.学习经验

1. 2810. 故障键盘(简单)

2810. 故障键盘 - 力扣（LeetCode）

思想

1.你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
2.不用字符串的反转函数，而是把反转完插入字符当做往字符串另一端后面插入字符，即首部和尾部都要插入字符，故想到双端队列。
然后双端队列天然的有迭代器begin().end()和rbegin(),rend(),所以可以直接放入string中，可以利用assign方法，或者直接利用string构造

代码

class Solution {
public:string finalString(string s) {int n = s.size();bool tag = true;deque<char> deq;for (int i = 0; i < n; ++i) {if (s[i] == 'i')tag = !tag;else if (tag) {deq.push_back(s[i]);} else {deq.push_front(s[i]);}}string res;if (tag)res.assign(deq.begin(), deq.end());elseres.assign(deq.rbegin(), deq.rend());return res;}
};

string构造

return tag ? string(deq.begin(), deq.end()): string(deq.rbegin(), deq.rend());

四、单调队列

1.套路

个人觉得叫单调双端队列更准确。
单调队列 = 滑动窗口 + 单调栈。
2.
问：入队、出队、更新答案，这三步的顺序如何思考？
答：有两种情况。
如果更新答案时，用到的数据包含当前元素，那么就需要先入队，再更新答案；
如果用到的数据不包含当前元素，那么就需要先更新答案，再入队。
至于出队，一般写在前面，每遍历到一个新的元素，就看看队首元素是否失效（不满足要求），失效则弹出队首。
$$\text{单调队列}\{\begin{array}{l}\text{双端队列}\{\begin{array}{l}\text{移除最左边的元素(不满足条件的无用数据/}\\ \text{不在窗口内的数据)}\\ \text{移除最右边的元素(不满足条件的无用数据)}\\ \text{在最右边插入元素(窗口向右滑动)}\end{array}\\ \text{单调性}\text{从队首到队尾单调递减(删除无用数据，}\\ \text{保证队列有序)}\end{array}$$
3.套路:

• 1.右边入(元素进入队尾，同时维护队列单调性)
• 2.左边出(元素离开队首)
• 3.记录/维护答案(根据队首)

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();vector<int> res(n - k + 1); // 窗口个数deque<int> deq;             // 双端队列// 枚举右端点for (int i = 0; i < n; ++i) {// 右边入while (!deq.empty() && nums[deq.back()] <= nums[i]) {deq.pop_back(); // 维护单调性}deq.push_back(i);// 左边出int left = i - k + 1; // 窗口左端点if (deq.front() < left)deq.pop_front();// 记录答案if (left >= 0)res[left] = nums[deq.front()]; // 队列从队首到队尾单调递减，队首就是窗口最大值}return res;}
};

2.题目描述

1(学习).给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值(答案) 。
2(重点学习).请设计一个自助结账系统(答案)，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：

• get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1
• add(value)：将价格为 value 的商品加入待结算商品队列的尾部
• remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1
  注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)
  3.给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度(答案)，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
  如果不存在满足条件的子数组，则返回 0 。
  4.给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：
• i，i + 1 ，…，j  表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。
  请你返回 不间断 子数组的总数目(答案)。
  子数组是一个数组中一段连续 非空 的元素序列。

3.学习经验

1.快速获得一个滑动窗口中的最值想到用单调队列

1. 239. 滑动窗口最大值(困难,学习)

239. 滑动窗口最大值 - 力扣（LeetCode）

思想

1.给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
2.此题要得到滑动窗口的最大值，首先滑动窗口肯定要左边出，右边进，而得到最大值最好维护一个单调性，所以想到单调队列。
按照套路:

• 1.右边入:不符合要求的元素右边出，维护单调性
• 2.左边出:不在窗口内的元素出
• 3.得到答案

代码

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();vector<int> res(n - k + 1); // 窗口个数deque<int> deq;             // 双端队列// 枚举右端点for (int i = 0; i < n; ++i) {// 右边入while (!deq.empty() && nums[deq.back()] <= nums[i]) {deq.pop_back(); // 维护单调性}deq.push_back(i);// 左边出int left = i - k + 1; // 窗口左端点if (deq.front() < left)deq.pop_front();// 记录答案if (left >= 0)res[left] = nums[deq.front()]; // 队列从队首到队尾单调递减，队首就是窗口最大值}return res;}
};

2. LCR 184.设计自助结算系统(中等,重点学习)

LCR 184. 设计自助结算系统 - 力扣（LeetCode）

思想

1.请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：

• get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1
• add(value)：将价格为 value 的商品加入待结算商品队列的尾部
• remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1
  注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)
  2.首先以O(1)入队和出队队列就能实现，难的是O(1)获得最大值。
  正常能想到用一个最大值变量维护，一个队列模拟，但是当该队列的最大值出栈时，最大值变量无法去找到下一个最大值进行更新，行不通。
  所以想到用一个单调队列来维护最大值，即一个单调的双端队列。
  只有当队列的队首跟单调队列的队首一样时，单调队列才移出队首。
  然后单调队列移入队尾时要维护单调性。

代码

class Checkout {
public:queue<int> que; // 维护原顺序deque<int> deq; // 维护最大值Checkout() {}int get_max() {if (deq.empty())return -1;return deq.front();}void add(int value) {que.push(value);while (!deq.empty() && deq.back() < value)deq.pop_back(); // 不是小于等于deq.push_back(value);}int remove() {if (que.empty())return -1;else if (que.front() == deq.front())deq.pop_front();int x = que.front();que.pop();return x;}
};/*** Your Checkout object will be instantiated and called as such:* Checkout* obj = new Checkout();* int param_1 = obj->get_max();* obj->add(value);* int param_3 = obj->remove();*/

3. 1438. 绝对差不超过限制的最长连续子数组(中等)

1438. 绝对差不超过限制的最长连续子数组 - 力扣（LeetCode）

思想

1.给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
2.首先，这是典型的不定长滑动窗口，是求最长类型。
然后要快速的得到滑动窗口的最大值和最小值，典型的单调队列，用两个单调队列，一个维护最大值，一个维护最小值，都记录下标。

代码

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {int n = nums.size();deque<int> deqMax;deque<int> deqMin;int l = 0, res = 0;for (int r = 0; r < n; ++r) {while (!deqMax.empty() && nums[deqMax.back()] < nums[r])deqMax.pop_back();while (!deqMin.empty() && nums[deqMin.back()] > nums[r])deqMin.pop_back();deqMax.push_back(r);deqMin.push_back(r);while (l <= r &&nums[deqMax.front()] - nums[deqMin.front()] > limit) {++l;if (!deqMax.empty() && deqMax.front() < l)deqMax.pop_front();if (!deqMin.empty() && deqMin.front() < l)deqMin.pop_front();}// [l,r]满足条件res = max(res, r - l + 1);}return res;}
};

4. 2762. 不间断子数组(中等)

2762. 不间断子数组 - 力扣（LeetCode）

思想

1.给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

• i，i + 1 ，…，j  表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。
  请你返回 不间断 子数组的总数目。
  子数组是一个数组中一段连续 非空 的元素序列。
  2.跟[[八、队列#3. 1438. 绝对差不超过限制的最长连续子数组(中等)]]一模一样，只不过答案从求长度最大值变成求子数组数目了。

代码

class Solution {
public:long long continuousSubarrays(vector<int>& nums) {int n = nums.size();long long res = 0;deque<int> deqMax;deque<int> deqMin;int l = 0;for (int r = 0; r < n; ++r) {while (!deqMax.empty() && nums[deqMax.back()] < nums[r])deqMax.pop_back();while (!deqMin.empty() && nums[deqMin.back()] > nums[r])deqMin.pop_back();deqMax.push_back(r);deqMin.push_back(r);while (l <= r && nums[deqMax.front()] - nums[deqMin.front()] > 2) {++l;if (!deqMax.empty() && deqMax.front() < l)deqMax.pop_front();if (!deqMin.empty() && deqMin.front() < l)deqMin.pop_front();}// [l,r]符合条件，共r-l+1个res += r - l + 1;}return res;}
};