給定一個(gè)數(shù)組 nums，有一個(gè)大小為?k?的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k?個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口中的最大值。

?

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]?
解釋:?

? 滑動(dòng)窗口的位置 ? ? ? ? ? ? ? ?最大值
--------------- ? ? ? ? ? ? ? -----
[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
?

提示：

你可以假設(shè) k 總是有效的，在輸入數(shù)組不為空的情況下，1 ≤ k ≤?輸入數(shù)組的大小。

?

進(jìn)階：

你能在線性時(shí)間復(fù)雜度內(nèi)解決此題嗎？

單調(diào)雙端隊(duì)列入門題。

入門

class Solution {ArrayDeque<Integer> deq = new ArrayDeque<Integer>();public void helper(int[] nums,int i, int k) {//刪除過期數(shù)據(jù)if (!deq.isEmpty() && deq.getFirst() == i - k)deq.removeFirst();//你比我早過期，還沒我大，要你何用while (!deq.isEmpty() && nums[i] > nums[deq.getLast()])deq.removeLast();//尾部插入新數(shù)字deq.addLast(i);}public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;if (n==0 || k == 0) return new int[0];int [] output = new int[n - k + 1];int index = 0;//前k-1個(gè)結(jié)尾沒答案，數(shù)字個(gè)數(shù)不夠for (int i = 0; i < k; i++) {helper(nums,i, k);//記錄第一個(gè)答案if (nums[i] > nums[index]) index = i;}//賦值第一個(gè)答案output[0] = nums[index];//繼續(xù)操作for (int i = k; i < n; i++) {helper(nums,i, k);output[i - k + 1] = nums[deq.getFirst()];}return output;} }

?

總結(jié)

以上是生活随笔為你收集整理的leetcode239. 滑动窗口最大值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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