题目形容
这是 LeetCode 上的 239. 滑动窗口最大值 ，难度为 艰难。
Tag :「优先队列（堆）」、「线段树」、「分块」、「枯燥队列」、「RMQ」
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右挪动一位。
返回滑动窗口中的最大值。
示例 1：
输出：nums = [1,3,-1,-3,5,3,6,7], k = 3
输入：[3,3,5,5,6,7]
解释：滑动窗口的地位 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7示例 2：
输出：nums = [1], k = 1
输入：[1]提醒：
- $1 <= nums.length <= 10^5$
- $-10^4 <= nums[i] <= 10^4$
- $1 <= k <= nums.length$
优先队列（堆）
依据题意，问题实质是 RMQ（Range Minimum/Maximum Query）区间最值问题。
容易想到优先队列（大根堆），同时为了确保滑动窗口的大小合法性，咱们以二元组 $(idx, nums[idx])$ 的模式进行入队。
当下标达到首个滑动窗口的右端点后，每次尝试从优先队列（大根堆）中取出最大值（若堆顶元素的下标小于以后滑动窗口左端点时，则抛弃该元素）。
代码：
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->b[1]-a[1]);
int n = nums.length, m = n - k + 1, idx = 0;
int[] ans = new int[m];
for (int i = 0; i < n; i++) {q.add(new int[]{i, nums[i]});
if (i >= k - 1) {while (q.peek()[0] <= i - k) q.poll();
ans[idx++] = q.peek()[1];
}
}
return ans;
}
}- 工夫复杂度：$O(n\log{n})$
- 空间复杂度：$O(n)$
线段树
容易将问题转换为「区间求和」问题：应用原始的 nums 构建线段树等价于在地位 $i$ 插入 $nums[i]$，即单点操作，而查问每个滑动窗口最大值，则对应的区间查问。
因为只波及单点批改，毋庸实现懒标记 pushdown 操作，再联合 $n$ 的数据范畴为 $10^5$，毋庸进行动静开点。
间接写 build 四倍空间的线段树数组实现即可。
代码：
class Solution {
class Node {
int l, r, val;
Node (int _l, int _r) {l = _l; r = _r; val = Integer.MIN_VALUE;}
}
Node[] tr = new Node[100010 * 4];
void build(int u, int l, int r) {tr[u] = new Node(l, r);
if (l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void update(int u, int x, int v) {if (tr[u].l == x && tr[u].r == x) {tr[u].val = Math.max(tr[u].val, v);
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) update(u << 1, x, v);
else update(u << 1 | 1, x, v);
pushup(u);
}
int query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
int mid = tr[u].l + tr[u].r >> 1, ans = Integer.MIN_VALUE;
if (l <= mid) ans = query(u << 1, l, r);
if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r));
return ans;
}
void pushup(int u) {tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);
}
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length, m = n - k + 1;
int[] ans = new int[m];
build(1, 1, n);
for (int i = 0; i < n; i++) update(1, i + 1, nums[i]);
for (int i = k; i <= n; i++) ans[i - k] = query(1, i - k + 1, i);
return ans;
}
}- 工夫复杂度：建设线段树复杂度为 $O(n\log{n})$；构建答案复杂度为 $O(n\log{n})$。整体复杂度为 $O(n\log{n})$
- 空间复杂度：$O(n)$
分块
另外一个做法是分块，又名「优雅的暴力」，也是莫队算法的根底。
具体的，除了给定的 nums 以外，咱们构建一个分块数组 region，其中 region[idx] = x 含意为块编号为 idx 的最大值为 x，其中一个块对应一个原始区间 $[l, r]$。
如何定义块大小是实现分块算法的要害。
对于本题，实质是求若干个大小为 $k$ 的区间最大值。
咱们能够设定块大小为 $\sqrt{k}$，这样所需创立的分块数组大小为 $\frac{n}{\sqrt{k}}$。分块数组的更新操作为 $O(1)$，而查问则为 $\sqrt{k}$。
容易证实查问操作的复杂度：对于每个长度为 $k$ 的 $[l, r]$ 查问操作而言，最多遍历两个（左右端点对应的块）的块内元素，复杂度为 $O(\sqrt{k})$，同时最多遍历 $\sqrt{k}$ 个块，复杂度同为 $O(\sqrt{k})$。
因而最多两步复杂度为 $O(\sqrt{k})$ 的块内操作，最多 $\sqrt{k}$ 步复杂度为 $O(1)$ 的块间操作，整体复杂度为 $O(\sqrt{k})$。
因而应用分块算法总的计算量为 $n\times\sqrt{k} = 10^6$，能够过。
分块算法的几个操作函数：
int getIdx(int x)：计算原始下标对应的块编号；void add(int x, int v)：计算原始下标x对应的下标idx，并将region[idx]和v取max来更新region[idx]；int query(int l, int r)：查问 $[l, r]$ 中的最大值，如果 $l$ 和 $r$ 所在块雷同，间接遍历 $[l, r]$ 进行取值；若 $l$ 和 $r$ 不同块，则解决 $l$ 和 $r$ 对应的块内元素后，对块编号在 $(getIdx(l), getIdx(r))$ 之间的块进行遍历。
代码：
class Solution {
int n, m, len;
int[] nums, region;
int getIdx(int x) {return x / len;}
void add(int x, int v) {region[getIdx(x)] = Math.max(region[getIdx(x)], v);
}
int query(int l, int r) {
int ans = Integer.MIN_VALUE;
if (getIdx(l) == getIdx(r)) {for (int i = l; i <= r; i++) ans = Math.max(ans, nums[i]);
} else {
int i = l, j = r;
while (getIdx(i) == getIdx(l)) ans = Math.max(ans, nums[i++]);
while (getIdx(j) == getIdx(r)) ans = Math.max(ans, nums[j--]);
for (int k = getIdx(i); k <= getIdx(j); k++) ans = Math.max(ans, region[k]);
}
return ans;
}
public int[] maxSlidingWindow(int[] _nums, int k) {
nums = _nums;
n = nums.length; len = (int) Math.sqrt(k); m = n / len + 10;
region = new int[m];
Arrays.fill(region, Integer.MIN_VALUE);
for (int i = 0; i < n; i++) add(i, nums[i]);
int[] ans = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) ans[i] = query(i, i + k - 1);
return ans;
}
}- 工夫复杂度：数组大小为 $n$，块大小为 $\sqrt{k}$，分块数组大小为 $\frac{n}{\sqrt{k}}$。预处理分块数组复杂度为 $O(n)$（即
add操作复杂度为 $O(1)$）；结构答案复杂度为 $O(n\times\sqrt{k})$（即query操作复杂度为 $O(\sqrt{k})$，最多有 $n$ 次查问） - 空间复杂度：$\frac{n}{\sqrt{k}}$
枯燥队列
对于 RMQ 的另外一个优良做法通常是应用「枯燥队列 / 枯燥栈」。
当然，咱们也能不依附教训，而从问题的自身登程，逐渐剖析出该做法。
假如咱们以后解决到某个长度为 $k$ 的窗口，此时窗口往后滑动一格，会导致后一个数（新窗口的右端点）增加进来，同时会导致前一个数（旧窗口的左端点）移出窗口。
随着窗口的一直平移，该过程会始终产生。若同一时刻存在两个数 $nums[j]$ 和 $nums[i]$（$j < i$）所在一个窗口内，下标更大的数会被更晚移出窗口，此时如果有 $nums[j] <= nums[i]$ 的话，能够齐全确定 $nums[j]$ 将不会成为后续任何一个窗口的最大值，此时能够将必然不会是答案的 $nums[j]$ 从候选中进行移除。
不难发现，当咱们将所有必然不可能作为答案的元素（即所有满足的小于等于 $nums[i]$）移除后，候选汇合满足「枯燥递加」个性，即汇合首位元素为以后窗口中的最大值（为了满足窗口长度为 $k$ 的要求，在从汇合头部取答案时须要先将下标小于的等于的 $i – k$ 的元素移除）。
为不便从尾部增加元素，从头部获取答案，咱们可应用「双端队列」存储所有候选元素。
代码：
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> d = new ArrayDeque<>();
int n = nums.length, m = n - k + 1;
int[] ans = new int[m];
for (int i = 0; i < n; i++) {while (!d.isEmpty() && nums[d.peekLast()] <= nums[i]) d.pollLast();
d.addLast(i);
if (i >= k - 1) {while (!d.isEmpty() && d.peekFirst() <= i - k) d.pollFirst();
ans[i - k + 1] = nums[d.peekFirst()];
}
}
return ans;
}
}- 工夫复杂度：$O(n)$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.239 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
本文由 mdnice 多平台公布