給你一個整數(shù)數(shù)組 nums，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)控汉。你只可以看到在滑動窗口內(nèi)的 k 個數(shù)字挤巡∠灯埃滑動窗口每次只向右移動一位拌倍。返回 滑動窗口中的最大值 箱季。
示例 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
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
思路一：利用雙端隊列(單調(diào)隊列)來實現(xiàn)涯穷，隊列從大到小排列，每次給尾部添加時都跟隊列中尾部的值對比藏雏，比要添加的小就刪除拷况；直到nums[隊尾]>nums[i] 為止，接下來添加掘殴；然后更新滑動窗口左邊索引赚瘦，并存儲最大值
時間復(fù)雜度： O(n)
空間復(fù)雜度： O(1)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//處理邊界條件
if(nums==null||nums.length==0||k<1) return new int[0];
if(k==1) return nums;
int[] maxes = new int[nums.length - (k-1)];
/**
創(chuàng)建雙端隊列(單調(diào)隊列)
使用：
peek:取值(偷偷瞄一眼) 等價于 get
poll:刪除(削) 等價于 remove
offer:添加(入隊) 等價于 add
*/
Deque<Integer> deque = new ArrayDeque<>();
for(int ri = 0; ri < nums.length;ri++) {
//1.如果nums[i] >= nums[隊尾]，就不斷刪除隊尾 直到nums[隊尾]>nums[i] 為止
while(!deque.isEmpty() && nums[ri] >= nums[deque.peekLast()]){
deque.pollLast();
}
//2.將i索引加入隊尾
deque.offerLast(ri);
//3. 如果wi>=0 先驗證有效性
int wi = ri - k + 1; //wi就是滑動窗口最左索引
if(wi<0) continue;
/**
1>如果隊頭失效奏寨，就移除隊頭(隊頭 < wi 就代表失效,因為隊頭在w索引的左邊 不在滑動窗口范圍內(nèi))
2>未失效起意，設(shè)置w窗口的最大值為nums[隊頭]
*/
if(deque.peekFirst() < wi) deque.pollFirst();
maxes[wi] = nums[deque.peekFirst()];
}
return maxes;
}
}
執(zhí)行結(jié)果.png
思路二： 暴力法，先求出第一個滑動窗口的最大值病瞳；設(shè)左右邊界揽咕，向右移動 每進來一個新值就跟最大值對比，更新當(dāng)前滑動窗口的最大值套菜；
注意：此方法在我2022年7月 實驗的時候已經(jīng)不適用了亲善，應(yīng)該是官方新增了測試用例，導(dǎo)致性能很低 跑完所有用例時間需要1000ms逗柴，屬于墊底的存在
//暴力法
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//處理邊界條件
if(nums==null||nums.length==0||k<1) return new int[0];
if(k==1) return nums;
int[] maxes = new int[nums.length - (k-1)];
//1.先求出第一段k各元素的最大值
int maxIdx = 0;
for(int i = 1; i < k; i++){
if(nums[i] >= nums[maxIdx]) maxIdx = I;
}
//2.li蛹头、ri 滑動左右邊界，對比求出最大值戏溺；得到結(jié)果后添加到數(shù)組
for(int li = 0; li < maxes.length;li++) {
int ri = li + k - 1;
//最大值索引不在滑動窗口范圍內(nèi)
if(maxIdx < li) {
//求最大值渣蜗，先假設(shè)li位置的是最大值
maxIdx = li;
for(int i = li+1 ;i <= ri;i++) {
if(nums[i] >= nums[maxIdx]) maxIdx = I;
}
}else if(nums[ri] >= nums[maxIdx]) {//在滑動窗口范圍內(nèi) && 大于等于新進來的值
maxIdx = ri;
}
//li:表示滑動窗口的索引
maxes[li] = nums[maxIdx];
}
return maxes;
}
}
