单调队列queue

1.单调队列（Monotonic Queue）

单调队列是一种特殊的队列，它的元素按照单调性（递增或递减）的顺序排列。简单来说，单调队列会维护一个元素单调递增或递减的顺序，在队列中元素会根据当前队列的元素和新加入的元素来进行更新。

基本概念

1. 单调递增队列：

   • 对于每个进入队列的元素，队列中的元素始终保持递增（从队头到队尾）。
   • 如果新元素小于队尾元素，队尾元素会被弹出，直到新元素大于或等于队尾元素。

2. 单调递减队列：

   • 与递增队列相反，队列中的元素始终保持递减（从队头到队尾）。
   • 如果新元素大于队尾元素，队尾元素会被弹出，直到新元素小于或等于队尾元素。

应用场景

1. 滑动窗口问题：

   • 常用于处理一些滑动窗口的最大值或最小值问题。
   • 如：给定一个数组，要求求出每个大小为k的滑动窗口内的最大值或最小值。

2. 范围查询：

   • 在一些区间问题中，可以通过单调队列高效地维护某些信息，如最大值或最小值。

单调队列的基本操作

• 插入元素：新元素进入队列时，如果它不满足单调性，需要将队尾的元素弹出，直到队列中的元素保持单调性。

• 弹出元素：元素离开队列时，队头的元素会被弹出。

• 获取队头元素：队头元素即为当前队列中最值（最大值或最小值）。

基本的单调队列实现（滑动窗口最大值）

#include <iostream>
#include <deque>
#include <vector>
using namespace std;vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;deque<int> dq;  // 存储窗口中的元素下标，队列是单调递减的for (int i = 0; i < nums.size(); i++) {// 弹出不在当前窗口内的元素if (!dq.empty() && dq.front() <= i - k) {dq.pop_front();}// 保持队列单调递减，弹出队尾小于当前元素的元素while (!dq.empty() && nums[dq.back()] <= nums[i]) {dq.pop_back();}// 将当前元素下标插入队列dq.push_back(i);// 当窗口大小达到 k 时，队头就是最大值if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;
}int main() {vector<int> nums = {1,3,-1,-3,5,3,6,7};int k = 3;vector<int> res = maxSlidingWindow(nums, k);for (int num : res) {cout << num << " ";}cout << endl;return 0;
}

 

代码解释

1. 队列维护：使用 deque<int> dq 来存储窗口中元素的下标。

   • 维护队列是单调递减的，即队列的队头是当前窗口的最大值对应的下标。

2. 窗口更新：

   • 每当移动窗口时，先移除不在窗口内的元素（即下标小于 i - k + 1 的元素）。
   • 然后确保队列中的元素是单调递减的，弹出队尾小于当前元素的元素。

3. 窗口内最大值：

   • 当窗口的大小达到 k 时，队头的元素对应的就是当前窗口的最大值，因此可以将 nums[dq.front()] 加入结果。

时间复杂度

• 时间复杂度：O(n)，其中 n 是数组的大小。每个元素最多入队一次，出队一次，因此时间复杂度是线性的。

• 空间复杂度：O(k)，队列最多存储 k 个元素的下标。

单调队列的拓展

除了在滑动窗口最大值问题中的应用，单调队列还可以应用于其他问题，下面是几个典型的扩展和优化。

1. 计算区间最小值/最大值

• 在给定区间内维护最大值或最小值，单调队列可以通过类似的方法帮助维护区间内的最值。

2. 单调队列解法的优化

• 优化查询和更新操作：一些问题中，查询操作和更新操作都可以在 O(1) 时间内完成，而对于较大的区间，可以通过分块和双指针的技巧进一步优化。

3. 维护多个窗口的最大值/最小值

• 可以使用多个单调队列，分别维护不同的窗口的最值，从而满足多个窗口的查询要求。

4. 最小栈与最大栈的扩展

• 在实现栈的最大值或最小值时，可以使用单调队列来优化栈内的查询。

复杂度优化

• 空间优化：对于一些问题，我们可以通过双端队列的变种来优化空间复杂度，避免额外的空间浪费。

---

总结

• 单调队列是一个非常强大的工具，特别适用于维护动态区间的最大值或最小值，常用于解决滑动窗口相关问题。
• 它的核心思想是利用队列保持元素的单调性，从而在窗口或区间中高效地获取最值。
• 在滑动窗口问题中，单调队列的应用使得时间复杂度可以优化到 O(n)，从而大大提高了效率。

2.题

1.算法竞赛进阶指南

思路：用bfs查找所有的方式

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>using namespace std;const int N = 4;
char graph[N][N];
int target = 0; // 目标状态，所有手柄都打开// 将当前状态转换为整数
int stateToInt(const char graph[N][N]) {int state = 0;for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {if (graph[i][j] == '-') {state |= (1 << (i * N + j));}}}return state;
}// 将整数转换回状态
void intToState(int state, char graph[N][N]) {for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {graph[i][j] = (state & (1 << (i * N + j))) ? '-' : '+';}}
}// 翻转手柄 [x, y] 及其所在行和列的所有手柄
void toggle(char graph[N][N], int x, int y) {for (int i = 0; i < N; ++i) {if (graph[x][i] == '+') graph[x][i] = '-';else graph[x][i] = '+';if (graph[i][y] == '+') graph[i][y] = '-';else graph[i][y] = '+';}if (graph[x][y] == '+') graph[x][y] = '-';else graph[x][y] = '+';
}struct State {int state;vector<pair<int, int>> moves;
};int main() {// 读取输入for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {cin >> graph[i][j];}}// 初始化目标状态target = (1 << (N * N)) - 1; // 所有手柄都打开的状态// 使用BFS寻找最短路径queue<State> q;unordered_map<int, bool> visited;int initialState = stateToInt(graph);q.push({initialState, {}});visited[initialState] = true;while (!q.empty()) {State current = q.front();q.pop();if (current.state == target) {cout << current.moves.size() << endl;for (auto& move : current.moves) {cout << move.first + 1 << " " << move.second + 1 << endl;}return 0;}for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {char tempGraph[N][N];intToState(current.state, tempGraph);toggle(tempGraph, i, j);int nextState = stateToInt(tempGraph);if (!visited[nextState]) {visited[nextState] = true;auto newMoves = current.moves;newMoves.emplace_back(i, j);q.push({nextState, newMoves});}}}}return 0;
}

 

2.

思路：模板题

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>using namespace std;void func(vector<int>& nums) {vector<int>dis(nums.size(), 0);stack<int>st;for (int i = 0; i < nums.size(); i++) {while (!st.empty() && nums[i] > nums[st.top()]) {dis[st.top()] = i + 1;st.pop();}st.push(i);}for (int i = 0; i < dis.size(); i++)cout << dis[i] << " ";
}int main() {int n; cin >> n;vector<int>nums(n, 0);for (int i = 0; i < n; i++)cin >> nums[i];func(nums);return 0;
}

3. 

思路：模板题

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>using namespace std;void func(vector<int>& nums) {vector<int>dis(nums.size(), 0);stack<int>st;for (int i = 0; i < nums.size(); i++) {while (!st.empty() && nums[i] > nums[st.top()]) {dis[st.top()] = i + 1;st.pop();}st.push(i);}for (int i = 0; i < dis.size(); i++) {cout << dis[i] << endl;}
}int main() {int n; cin >> n;vector<int>nums(n, 0);for (int i = 0; i < n; i++)cin >> nums[i];func(nums);return 0;
}

4 .

 

思路：根据题意结合单调栈即可

#include <iostream>
#include<cstdio>
#include <vector>
#include <stack>
#include <algorithm>using namespace std;#define ll unsigned long 
ll ans, x, n;struct f {ll s, i;
};
stack<f> st;int main(){cin >> n;for (ll i = 1; i <= n; i++){cin >> x;while (!st.empty() && x >= st.top().s){ans ^= st.top().i;st.pop();}st.push({ x, i });ans ^= i;cout << ans << endl;}return 0;
}

5.

思路： 用俩个单调栈，一个递增，一个递减，在用upper_bound来找位置，通过max确定最大值

#include <cstdio>
#include <set>
#include <algorithm>const int maxn = 100005;int n, ans, tx, tn;
int a[maxn], sx[maxn], sn[maxn];int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", a + i);for (int i = 1; i <= n; ++i) {while (tn && a[sn[tn]] >= a[i]) --tn;while (tx && a[sx[tx]] < a[i]) --tx;int k = std::upper_bound(sn + 1, sn + 1 + tn, sx[tx]) - sn;if (k != (tn + 1)) {ans = std::max(ans, i - sn[k] + 1);}sn[++tn] = i;sx[++tx] = i;}printf("%d\n", ans);return 0;
}

6.

思路： i 左右俩边是不是有一样的人，有same【i】++，同时一样高的人也是面对面，也++

#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;long long n,s[500010],a[500010],top,sum,same[500010];
int main(){cin>>n;for(int i=1; i<=n; i++)scanf("%d",&a[i]);for(int i=1; i<=n; i++){while(top>0&&a[i]>=a[s[top-1]]){if(a[i]==a[s[top-1]])same[i]=same[s[top-1]]+1;sum++;sum+=same[s[top-1]];top--;}if(top>0)sum++;s[top++]=i;}cout<<sum;return 0;
}

7.

思路： 方向用单调栈来解题，模板题

#include <iostream>
#include <vector>
#include <stack>using namespace std;int main() {int n;cin >> n;vector<int> h(n);for (int i = 0; i < n; i++) {cin >> h[i];}stack<int> st;long long total = 0;for (int i = n - 1; i >= 0; i--) {while (!st.empty() && h[st.top()] < h[i]) {st.pop();}if (!st.empty()) {total += st.top() - i - 1;} else {total += n - i - 1;}st.push(i);}cout << total << endl;return 0;
}

 8.

思路：单调队列的模板题

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include<queue>using namespace std;void func(vector<int>& nums, int k) {vector<int> result;deque<int> dq;for (int i = 0; i < nums.size(); i++) {if (!dq.empty() && dq.front() <= i - k) dq.pop_front();while (!dq.empty() && nums[dq.back()] >= nums[i]) dq.pop_back();dq.push_back(i);if (i >= k - 1) result.push_back(nums[dq.front()]);}for (int i = 0; i < result.size(); i++)cout << result[i] << " ";cout << endl;result.clear(); dq.clear();for (int i = 0; i < nums.size(); i++) {if (!dq.empty() && dq.front() <= i - k)  dq.pop_front();while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();dq.push_back(i);if (i >= k - 1) result.push_back(nums[dq.front()]);}for (int i = 0; i < result.size(); i++)cout << result[i] << " ";
}int main() {int n, m; cin >> n >> m;vector<int>nums(n, 0);for (int i = 0; i < n; i++)cin >> nums[i];func(nums, m);return 0;
}

9. 

 

思路：卡了好久的题，用二分答案+单调队列移动窗口来写

#include <bits/stdc++.h>
using namespace std;int n, D, l, r;
struct WATER {int x, y;
} p[100010];int ans = 2100000000;
int q1[100010], q2[100010];
int p1[100010], p2[100010];
int head1 = 1, tail1 = 1, head2 = 1, tail2 = 1;bool check(int k) {int L = 1;q1[1] = p[1].y;p1[1] = p[1].x;q2[1] = p[1].y;p2[1] = p[1].x;head1 = 1, tail1 = 1, head2 = 1, tail2 = 1; // 初始化队列和 head，tailfor (int i = 2; i <= n; i++) {while ((p[i].x - p[L].x) > k) L++; // 控制左端可以到哪while (p1[head1] < p[L].x && head1 <= tail1) // 队头出队head1++;while (p2[head2] < p[L].x && head2 <= tail2) // 队头出队head2++;while (q1[tail1] <= p[i].y && head1 <= tail1) // 队尾出队tail1--;p1[++tail1] = p[i].x;q1[tail1] = p[i].y; // 队尾入队while (q2[tail2] >= p[i].y && head2 <= tail2) // 队尾出队tail2--;p2[++tail2] = p[i].x;q2[tail2] = p[i].y; // 队尾入队if ((q1[head1] - q2[head2]) >= D) return 1; // 如果时间差满足条件}return 0;
}bool cmp(WATER a, WATER b) {return a.x < b.x; // 按 x 坐标升序排列
}int main() {scanf("%d%d", &n, &D);for (int i = 1; i <= n; i++) {scanf("%d%d", &p[i].x, &p[i].y);}l = 0, r = 1000010;sort(p + 1, p + n + 1, cmp); // 按 x 坐标升序排序while (l <= r) { // 二分查找宽度int mid = (l + r) / 2;if (check(mid)) { // 如果当前宽度可以满足要求r = mid - 1;ans = min(ans, mid);} else {l = mid + 1;}}if (ans == 2100000000) printf("-1");else printf("%d", ans);return 0;
}

10. 

思路：看的题解思路写的

思路：我们首先需要用一个map去统计每个数出现的次数，然后快排一下，去重，跑一遍单调队列，我们在单调队列中去处理结果

我们用sum去表示过程中的值，ans表示最终的最大值

如果队列不为空并且当前要插入的元素和队尾元素差值不是1，那么去更新最大值，然后将sum变为0 

如果队列不为空，但是插入的值和第一个元素的值差值大于等于k，说明插入的元素要多于k了，因此我们需要将队首元素弹出，并且sum-队首元素的次数

#include<bits/stdc++.h>
using namespace std;int t;
int n, k;
int a[200005];
map<int, int> mp;struct node{int x;int cnt;
};
deque<node> que;
void solve(){cin >> n >> k;mp.clear();for(int i = 1; i <= n; i++) {cin >> a[i];mp[a[i]]++;}sort(a + 1, a + 1 + n);int len = unique(a + 1, a + 1 + n) - (a + 1);vector<node> q(len + 1);for(int i = 1; i <= len; i++) {q[i].x = a[i];q[i].cnt = mp[a[i]];}int sum = 0;int ans = 0;for(int i = 1; i <= len; i++){if (!que.empty() && q[i].x - 1 != que.back().x){ans = max(ans, sum);sum = 0;while (!que.empty()) {que.pop_back();}}while (!que.empty() && que.front().x<=q[i].x-k){ans = max(ans, sum);sum -= que.front().cnt;que.pop_front();}que.push_back(q[i]);sum += q[i].cnt;ans = max(ans, sum);}cout << ans << "\n";while (!que.empty()){que.pop_back();}
}signed main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> t;while (t--)solve();return 0;
}