文章目錄

• 1理解題目
• 2 思路
• • 2.1暴力求解
  • 2.2雙端隊列

1理解題目

輸入：整數數組nums，滑動窗口大小k
輸出：整數數組
規則：在一個窗口內只能看到k個數，找一個最大的數，添加到返回數組中。每次滑動向右滑動一步。

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max

---

[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 思路

2.1暴力求解

只能想到暴力的思路。每次窗口范圍內比較k個元素大小。所以時間復雜度是O(nk)。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums==null || nums.length==0) return null;if(k==0) return nums;int n = nums.length;int[] r = new int[n-k+1];for(int i=0;i<n-k+1;i++){r[i] = nums[i];for(int j=i;j<i+k;j++){r[i] = Math.max(r[i],nums[j]);}}return r;}}

2.2雙端隊列

看了力扣官方解釋想起來了，當時做的時候確實蒙圈。

隊列是一個雙端隊列。隊列中存放的是當前窗口內的k個元素的下標。注意這里不存元素，存下標。隊列頭部的元素是窗口范圍內，最大值元素的下標。例如：nums=[1,3,-1,-3,5,3,6,7] ,在{-1,-3,5}這個窗口范圍內，隊列頭部存放的元素值是4。隊列尾部存放的元素是當前窗口內最大值元素的下標。最大值是5，下標是4。
每次添加下標為i的元素的時候：
1 檢查隊列頭部元素是不是等于i-k。是，就刪除。
2 不斷拿nums[i]與隊尾元素比較。如果nums[i]>nums[隊尾元素]，則刪除隊尾元素，在隊尾插入i。否則不做任何操作。
隊列中元素的nums值是不斷遞減的。

class Solution {private ArrayDeque<Integer> deq = new ArrayDeque<Integer>();private int[] nums;private int k;public int[] maxSlidingWindow(int[] nums, int k) {if(nums==null || nums.length==0) return null;if(k==0) return nums;int n = nums.length;this.nums = nums;this.k = k;int[] r = new int[n-k+1];deq = new ArrayDeque<Integer>();for(int i=0;i<k;i++){add(i);}r[0] = nums[deq.getFirst()];for(int i=k;i<n;i++){add(i);r[i-k+1] = nums[deq.getFirst()];}return r;}private void add(int i){if(!deq.isEmpty() && deq.getFirst()==i-k){deq.removeFirst();}while(!deq.isEmpty() && nums[deq.getLast()]<nums[i]){deq.removeLast();}deq.addLast(i);} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的239. Sliding Window Maximum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。