滑動窗口問題

---

滑動窗口解決思路

生成窗口最大值數(shù)組

求一個數(shù)組中最大值減去最小值小于或等于 num 的子數(shù)組數(shù)量

---

1. 滑動窗口解決思路

準(zhǔn)備一個雙端隊列，雙端隊列存放著數(shù)組中的下標(biāo)值。

假設(shè)當(dāng)前為 arr[i]，則放入規(guī)則如下：

• left 和 right 指針都只會向右移動，不會回退。
• right 右滑，窗口加數(shù)：
  1）如果 queue 為空，直接把下標(biāo) i 放入 queue 中；
  2）如果 queue 不為空，取出當(dāng)前 queue 隊尾存放的下標(biāo) j。如果 arr[j] > arr[i]，則直接把 i 放入隊尾；
  3）如果 arr[j] <= arr[i]，則一直從 queue 的隊尾彈出下標(biāo)，直到某個下標(biāo)在 queue 中的對應(yīng)值大于 arr[i]，然后把 i 放入隊尾
• left 右滑，窗口減數(shù)：
  1）看彈出的 left 是否與隊列頭相等，如果相等，說明這個隊列頭已經(jīng)不在窗口內(nèi)了，所以彈出 queue 當(dāng)前的隊首元素 。

雙端隊列的隊頭就是當(dāng)前窗口最大值的下標(biāo)。

---

2. 生成窗口最大值數(shù)組

題目描述：【題目】有一個整形數(shù)組arr和一個大小為w的窗口從數(shù)組的最左邊滑到最右邊，窗口每次向最右邊滑一個位置。

例如，數(shù)組為[4,3,5,4,3,3,6,7],窗口大小為3時，

[4 3 5] 4 3 3 6 7 窗口最大值為5

4 [3 5 4] 3 3 6 7 窗口最大值為5

4 3 [5 4 3] 3 6 7 窗口最大值為5

4 3 5 [4 3 3] 6 7 窗口最大值為4

4 3 5 4 [3 3 6] 7 窗口最大值為6

4 3 5 4 3 [3 6 7] 窗口最大值為7

如果數(shù)組長度為n,窗口大小為w，則一共產(chǎn)生n-w+1個窗口的最大值。請實現(xiàn)一個函數(shù)：

輸入：整型數(shù)組arr, 窗口大小為w.

輸出：一個長度為n-w+1的數(shù)組res，res[i]表示每一種窗口狀態(tài)下的最大值。

以本題為例，結(jié)果應(yīng)該返回{5,5,5,4,6,7}。

public static int[] getMaxWindow(int[] arr, int w) {if (arr == null || w < 1 || arr.length < w) {return null;}LinkedList<Integer> qmax = new LinkedList();int[] res = new int[arr.length - w + 1];int index = 0;for (int i = 0; i < arr.length; i++) {while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {qmax.pollLast();}qmax.addLast(i);if (qmax.peekFirst() == i - w) {qmax.pollFirst();}if (i >= w - 1) {res[index++] = arr[qmax.peekFirst()];}}return res;}

---

3. 求一個數(shù)組中最大值減去最小值小于或等于 num 的子數(shù)組數(shù)量

public static int getNum(int[] arr, int num) {if (arr == null || arr.length == 0) {return 0;}LinkedList<Integer> qmin = new LinkedList<>();LinkedList<Integer> qmax = new LinkedList<>();int L = 0;int R = 0;int res = 0;while (L < arr.length) {while (R < arr.length) {if (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {qmin.pollLast();}qmin.addLast(R);if (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {qmax.pollLast();}qmax.addLast(R);if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {break;}R++;}if (qmin.peekFirst() == L) {qmin.pollFirst();}if (qmax.peekFirst() == L) {qmax.pollFirst();}res += R - L;L++;}return res;}

總結(jié)

以上是生活随笔為你收集整理的滑动窗口问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。