苗木公司网站模板,河南省建设工程注册中心网站,站长工具手机综合查询,做网站在哪里找客户1.单调队列#xff08;Monotonic Queue#xff09;
单调队列是一种特殊的队列#xff0c;它的元素按照单调性#xff08;递增或递减#xff09;的顺序排列。简单来说#xff0c;单调队列会维护一个元素单调递增或递减的顺序#xff0c;在队列中元素会根据当前队列的元素…1.单调队列Monotonic Queue
单调队列是一种特殊的队列它的元素按照单调性递增或递减的顺序排列。简单来说单调队列会维护一个元素单调递增或递减的顺序在队列中元素会根据当前队列的元素和新加入的元素来进行更新。
基本概念 单调递增队列 对于每个进入队列的元素队列中的元素始终保持递增从队头到队尾。如果新元素小于队尾元素队尾元素会被弹出直到新元素大于或等于队尾元素。 单调递减队列 与递增队列相反队列中的元素始终保持递减从队头到队尾。如果新元素大于队尾元素队尾元素会被弹出直到新元素小于或等于队尾元素。
应用场景 滑动窗口问题 常用于处理一些滑动窗口的最大值或最小值问题。如给定一个数组要求求出每个大小为k的滑动窗口内的最大值或最小值。 范围查询 在一些区间问题中可以通过单调队列高效地维护某些信息如最大值或最小值。
单调队列的基本操作 插入元素新元素进入队列时如果它不满足单调性需要将队尾的元素弹出直到队列中的元素保持单调性。 弹出元素元素离开队列时队头的元素会被弹出。 获取队头元素队头元素即为当前队列中最值最大值或最小值。
基本的单调队列实现滑动窗口最大值
#include iostream
#include deque
#include vector
using namespace std;vectorint maxSlidingWindow(vectorint nums, int k) {vectorint result;dequeint 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() {vectorint nums {1,3,-1,-3,5,3,6,7};int k 3;vectorint res maxSlidingWindow(nums, k);for (int num : res) {cout num ;}cout endl;return 0;
}代码解释 队列维护使用 dequeint dq 来存储窗口中元素的下标。 维护队列是单调递减的即队列的队头是当前窗口的最大值对应的下标。 窗口更新 每当移动窗口时先移除不在窗口内的元素即下标小于 i - k 1 的元素。然后确保队列中的元素是单调递减的弹出队尾小于当前元素的元素。 窗口内最大值 当窗口的大小达到 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_mapusing 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;vectorpairint, 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寻找最短路径queueState q;unordered_mapint, 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 algorithmusing namespace std;void func(vectorint nums) {vectorintdis(nums.size(), 0);stackintst;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;vectorintnums(n, 0);for (int i 0; i n; i)cin nums[i];func(nums);return 0;
}
3. 思路模板题
#include iostream
#include vector
#include stack
#include algorithmusing namespace std;void func(vectorint nums) {vectorintdis(nums.size(), 0);stackintst;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;vectorintnums(n, 0);for (int i 0; i n; i)cin nums[i];func(nums);return 0;
}
4 . 思路根据题意结合单调栈即可
#include iostream
#includecstdio
#include vector
#include stack
#include algorithmusing namespace std;#define ll unsigned long
ll ans, x, n;struct f {ll s, i;
};
stackf 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 algorithmconst 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】同时一样高的人也是面对面也
#includeiostream
#includecstdio
#includealgorithmusing namespace std;long long n,s[500010],a[500010],top,sum,same[500010];
int main(){cinn;for(int i1; in; i)scanf(%d,a[i]);for(int i1; in; i){while(top0a[i]a[s[top-1]]){if(a[i]a[s[top-1]])same[i]same[s[top-1]]1;sum;sumsame[s[top-1]];top--;}if(top0)sum;s[top]i;}coutsum;return 0;
}
7. 思路 方向用单调栈来解题模板题
#include iostream
#include vector
#include stackusing namespace std;int main() {int n;cin n;vectorint h(n);for (int i 0; i n; i) {cin h[i];}stackint 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
#includequeueusing namespace std;void func(vectorint nums, int k) {vectorint result;dequeint 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;vectorintnums(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; // 初始化队列和 headtailfor (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-队首元素的次数
#includebits/stdc.h
using namespace std;int t;
int n, k;
int a[200005];
mapint, int mp;struct node{int x;int cnt;
};
dequenode 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);vectornode 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().xq[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;
}
