为了更好的浏览体验，欢送浏览原文：
[[思维晋升|干货All in]6种算法解决LeetCode艰难题：滑动窗口最大值 (eriktse.com)](https://www.eriktse.com/algorithm/1039.html)
最近在leetcode遇到一道十分经典的题目：239. 滑动窗口最大值 - 力扣（LeetCode）
以前只会看题解用枯燥队列做，最近钻研一下发现是一道很好的题，能够帮忙咱们晋升“保护区间最值”的算法思维。
先介绍一下我解决这题所用的算法及其复杂度：
- 枯燥队列 O(n)
- st表 O(nlogn)
- 树状数组 O(n(logn)^2)
- 多重集非法 O(nlogn)
- 莫队O (n sqrt{n})
- 优先队列 O(nlogn)
首先确定一点，枯燥队列是解决这道题最好的方法，然而其余的办法的适用范围更广。
1、枯燥队列
首先能够参考几篇优良的文章：
算法学习笔记(66): 枯燥队列 - 知乎 (zhihu.com)
枯燥队列 - OI Wiki (oi-wiki.org)
我这里提几点值得注意的中央：
1.枯燥队列中寄存的是下标，而不是元素值
2.枯燥队列是一个双端队列，尾插前先查队头后查队尾
3.枯燥队列保护的是元素值的枯燥性
有了这几点留神，代码就很好写了：
class Solution {public: static const int maxn = 1e5 + 9; int a[maxn]; deque<int> dq; vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> res; int n = nums.size(); for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1]; for(int i = 1;i <= n; ++ i) { int x = a[i]; while(!dq.empty() and dq.front() < i - k + 1)dq.pop_front(); while(!dq.empty() and x >= a[dq.back()])dq.pop_back(); dq.push_back(i); if(i >= k)res.push_back(a[dq.front()]); } return res; }};我做题习惯把输出数组存一个array，大家请勿介意。
2.st表
st表是一种基于DP（动静布局）思维的算法，也算是一种数据结构吧。
st表能够动态保护区间的最值，须要用的工夫来预处理，后能够O(1)查问。
咱们定义dpi示意
示意区间的最值，在这道题里咱们认为是最大值（保护最小值同理）。看一下能不能开下，大略是maxn * 20的大小，能够开下。
通过定义不难发现，dpi = a[i]，因为此时区间长度为1，那么最值就是元素a[i]自身。当j增大时，咱们有转移方程（具体的起因可简略自行推导，当前的文章中也会有解说）：
dpi = max(dpi, dpi + 2^(j-1))
查问非常不便，办法是从两边往两头尽可能多地笼罩。假如要查问的区间是[l,r]
，那么咱们能够失去区间长度r - l + 1，当初求一个比长度小且最大的2的幂，而后把左右两块取大即可。
间接看代码：
class Solution {public: static const int maxn = 1e5 + 9; int a[maxn], st[maxn][30];//st[i][j]示意[i, i + 2^j - 1]的最大值 int queMax(int l, int r) { int k = log(r - l + 1) / log(2); return max(st[l][k], st[r - (1<<k) + 1][k]); } vector<int> maxSlidingWindow(vector<int>& nums, int k) { memset(st, 0xcf, sizeof st); vector<int> res; int n = nums.size(); for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1]; for(int i = 1;i <= n; ++ i)st[i][0] = a[i]; for(int k = 1;k <= 20; ++ k) { for(int i = 1;i <= n and i + (1 << (k - 1)) <= n; ++ i) { st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]); } } for(int i = 1;i + k - 1 <= n; ++ i)res.push_back(queMax(i, i + k - 1)); return res; }};3、树状数组
看见树状数组可能有小朋友会感到纳闷了哦，树状数组不是保护区间和的吗？怎么还来凑“区间最值”的冷落了。
其实树状数组不仅能够保护区间和，还能够“动静保护区间最值”，然而保护的办法和区间和略有不同。这一次次要看一下代码吧，具体的原理之后再讲。
树状数组节点t[k]保护的是区间[k - lowbit(k) + 1, k]。
树状数组次要突出的长处就是能够动静保护，然而留神在保护区间最值的时候仅可单点批改，不反对区间批改。
class Solution {public: static const int maxn = 1e5 + 9; //树状数组 int a[maxn], t[maxn], n;//t[i] 示意 a[i - lowbit(i) + 1] ~ a[i]的最大值 int lowbit(int x){return x & -x;} void update(int k, int x)// modify a[k] to x { a[k] = x; while(k <= n) { t[k] = x; for(int i = 1;i < lowbit(k); i <<= 1)t[k] = max(t[k], t[k - i]); k += lowbit(k); } } int queMax(int l, int r) { int res = a[r];//单点查问 while(l <= r) { for(;r - lowbit(r) >= l; r -= lowbit(r))res = max(res, t[r]); res = max(res, a[r --]); } return res; } vector<int> maxSlidingWindow(vector<int>& nums, int k) { n = nums.size(); for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1]; vector<int> res; for(int i = 1;i <= n; ++ i) { update(i, a[i]); if(i >= k)res.push_back(queMax(i - k + 1, i)); } return res; }};4、多重集非法
这种办法就非常简略粗犷了，就是保护一个一直挪动的multiset，几乎是暴力之王。
class Solution {public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { multiset<int> st; vector<int> res; for(int i = 0;i < k; ++ i)st.insert(nums[i]); res.push_back(*st.rbegin()); for(int i = k;i < nums.size(); ++ i) { st.erase(st.find(nums[i - k])); st.insert(nums[i]); res.push_back(*st.rbegin()); } return res; }};5、莫队
莫队须要基于multiset，在这道题里的劣势并不显著，因为这题的询问都是有程序的，然而能够写个莫队练个手。
莫队在解决随机区间查问问题的时候有独特的劣势，因为足够暴力，所以保护的货色能够很多很杂，比方区间和，区间最值，区间元素品种数等。
当前我会具体讲莫队的，欢送大家拜访我的集体博客：https://www.eriktse.com
在右上角留下邮箱订阅我的博客，每周更新优质的算法/技术/互联网文章！
class Solution {public: static const int maxn = 1e5 + 9; int a[maxn], pos[maxn], ans[maxn], n; struct Q { int l, r, id;//询问离线 }q[maxn];//outline algorihm multiset<int> st; void Add(int k)//把a[k]退出到区间内 { st.insert(a[k]); } void Del(int k) { st.erase(st.find(a[k])); } vector<int> maxSlidingWindow(vector<int>& nums, int k) { n = nums.size(); for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1]; int siz = sqrt(n); for(int i = 1;i <= n; ++ i)pos[i] = i / siz; int m = n - k + 1; for(int i = 1;i <= m; ++ i)q[i].l = i, q[i].r = i + k - 1, q[i].id = i; sort(q + 1, q + 1 + m, [this](const Q &u, const Q &v) { return pos[u.l] == pos[v.l] ? u.r < v.r : pos[u.l] < pos[v.l]; }); int L = 1, R = 0;//以后区间 for(int i = 1;i <= m; ++ i) { //[L, R] -> [l, r] int l = q[i].l, r = q[i].r, id = q[i].id; while(L < l)Del(L ++); while(L > l)Add(-- L); while(R > r)Del(R --); while(R < r)Add(++ R); ans[id] = *st.rbegin(); } vector<int> res; for(int i = 1;i <= m; ++ i)res.push_back(ans[i]); return res; }};6、优先队列
优先队列能够了解为一个“堆”构造。
咱们晓得优先队列能够保护最值，然而他只有一个堆顶怎么办呢？
咱们只能保障堆顶是最大值然而却无奈保障堆顶是在窗口内的呀！
为了解决这个问题，咱们在每一次查问堆顶之前，都要对堆顶进行查看，直到堆顶在窗口内能力输入。
留神以下几点：
1.堆里寄存的是下标，然而比拟函数用值比拟。
2.每次取出元素之前堆顶查看，只有堆顶的地位不在窗口内就始终弹出。
上代码！
const int maxn = 1e5 + 9;int a[maxn];class Solution {public: struct cmp{ bool operator ()(const int &u, const int &v)const { return a[u] < a[v]; } }; priority_queue<int, vector<int>, cmp> pq; vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1]; vector<int> res; for(int i = 1;i <= n; ++ i) { pq.push(i); while(!pq.empty() and pq.top() < i - k + 1)pq.pop(); if(i >= k)res.push_back(a[pq.top()]); } return res; }};