題目及測試
package pid239;
/*滑動視窗最大值
給定一個數組 nums，有一個大小為 k 的滑動視窗從數組的最左側移動到數組的最右側。你隻可以看到在滑動視窗内的 k 個數字。滑動視窗每次隻向右移動一位。
傳回滑動視窗中的最大值。
示例:
輸入: 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
提示：
你可以假設 k 總是有效的，在輸入數組不為空的情況下，1 ≤ k ≤ 輸入數組的大小。
進階：
你能線上性時間複雜度内解決此題嗎？
*/
public class main {
public static void main(String[] args) {
int[][] testTable = {{1,1,2},{1,1,2,2,5,6,7,7},{1,2,3,5},{-1,1,1,1}};
int[] testTable2={3,7,4,0};
for (int i=0;i<testTable.length;i++) {
test(testTable[i],testTable2[i]);
}
}
private static void test(int[] ito,int ito2) {
Solution solution = new Solution();
int[] rtn;
long begin = System.currentTimeMillis();
for (int i = 0; i < ito.length; i++) {
System.out.print(ito[i]+" ");
}//開始時列印數組
System.out.println("ito2= "+ito2);
rtn = solution.maxSlidingWindow(ito,ito2);//執行程式
long end = System.currentTimeMillis();
for (int i = 0; i < rtn.length; i++) {
System.out.print(rtn[i]+" ");
}//列印結果幾數組
System.out.println();
System.out.println("耗時：" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
沒想出來
解法1（别人的）
這是另一個 O(N)的算法。本算法的優點是不需要使用 數組 / 清單 之外的任何資料結構。
算法的思想是将輸入數組分割成有 k 個元素的塊。
若 n % k != 0，則最後一塊的元素個數可能更少。
開頭元素為 i ，結尾元素為 j 的目前滑動視窗可能在一個塊内，也可能在兩個塊中。
情況 1 比較簡單。 建立數組 left， 其中 left[j] 是從塊的開始到下标 j 最大的元素，方向 左->右。
為了處理更複雜的情況 2，我們需要數組 right，其中 right[j] 是從塊的結尾到下标 j 最大的元素，方向 右->左。right 數組和 left 除了方向不同以外基本一緻。
兩數組一起可以提供兩個塊内元素的全部資訊。考慮從下标 i 到下标 j的滑動視窗。 根據定義，right[i] 是左側塊内的最大元素， left[j] 是右側塊内的最大元素。是以滑動視窗中的最大元素為 max(right[i], left[j])。
算法
算法十分直截了當：
從左到右周遊數組，建立數組 left。
從右到左周遊數組，建立數組 right。
建立輸出數組 max(right[i], left[i + k - 1])，其中 i 取值範圍為 (0, n - k + 1)。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
if (k == 1) return nums;
int [] left = new int[n];
left[0] = nums[0];
int [] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
// from left to right
if (i % k == 0) left[i] = nums[i]; // block_start
else left[i] = Math.max(left[i - 1], nums[i]);
// from right to left
int j = n - i - 1;
if ((j + 1) % k == 0) right[j] = nums[j]; // block_end
else right[j] = Math.max(right[j + 1], nums[j]);
}
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++)
output[i] = Math.max(left[i + k - 1], right[i]);
return output;
}
}
解法2（别人的）
優先隊列
對于「最大值」，我們可以想到一種非常合适的資料結構，那就是優先隊列（堆），其中的大根堆可以幫助我們實時維護一系列元素中的最大值。
對于本題而言，初始時，我們将數組 nums 的前 k 個元素放入優先隊列中。每當我們向右移動視窗時，我們就可以把一個新的元素放入優先隊列中，此時堆頂的元素就是堆中所有元素的最大值。然而這個最大值可能并不在滑動視窗中，在這種情況下，這個值在數組 nums中的位置出現在滑動視窗左邊界的左側。是以，當我們後續繼續向右移動視窗時，這個值就永遠不可能出現在滑動視窗中了，我們可以将其永久地從優先隊列中移除。
我們不斷地移除堆頂的元素，直到其确實出現在滑動視窗中。此時，堆頂元素就是滑動視窗中的最大值。為了友善判斷堆頂元素與滑動視窗的位置關系，我們可以在優先隊列中存儲二進制組 (num,index)，表示元素 num 在數組中的下标為 index。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
解法3（别人的）
單調隊列
我們可以順着方法一的思路繼續進行優化。
由于我們需要求出的是滑動視窗的最大值，如果目前的滑動視窗中有兩個下标 i 和 j，其中 i 在 j 的左側（i<j），并且 i 對應的元素不大于 j 對應的元素（nums[i]≤nums[j]），那麼會發生什麼呢？
當滑動視窗向右移動時，隻要 i 還在視窗中，那麼 j 一定也還在視窗中，這是 i 在 j 的左側所保證的。是以，由于 nums[j] 的存在，nums[i] 一定不會是滑動視窗中的最大值了，我們可以将 nums[i] 永久地移除。
是以我們可以使用一個隊列存儲所有還沒有被移除的下标。在隊列中，這些下标按照從小到大的順序被存儲，并且它們在數組 nums 中對應的值是嚴格單調遞減的。因為如果隊列中有兩個相鄰的下标，它們對應的值相等或者遞增，那麼令前者為 i，後者為 j，就對應了上面所說的情況，即 nums[i] 會被移除，這就産生了沖突。
當滑動視窗向右移動時，我們需要把一個新的元素放入隊列中。為了保持隊列的性質，我們會不斷地将新的元素與隊尾的元素相比較，如果前者大于等于後者，那麼隊尾的元素就可以被永久地移除，我們将其彈出隊列。我們需要不斷地進行此項操作，直到隊列為空或者新的元素小于隊尾的元素。
由于隊列中下标對應的元素是嚴格單調遞減的，是以此時隊首下标對應的元素就是滑動視窗中的最大值。但與方法一中相同的是，此時的最大值可能在滑動視窗左邊界的左側，并且随着視窗向右移動，它永遠不可能出現在滑動視窗中了。是以我們還需要不斷從隊首彈出元素，直到隊首元素在視窗中為止。
為了可以同時彈出隊首和隊尾的元素，我們需要使用雙端隊列。滿足這種單調性的雙端隊列一般稱作「單調隊列」。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}