題目描述
給定一個陣列 nums 和滑動視窗的大小 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 ≤ 輸入陣列的大小，
題解
單調佇列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0) return new int[0];
int[] q = new int[nums.length];
int[] arr = new int[nums.length - k + 1];
int l = 0, r = -1;
for(int i = 0; i < nums.length; i++){
while(l <= r && i - q[l] + 1 > k) l++;
while(l <= r && nums[i] >= nums[q[r]])r--;
q[++r] = i;
if(i >= k - 1)
arr[i - k + 1] = nums[q[l]];
}
return arr;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/267419.html
標籤：其他
上一篇：【每日藍橋】25、一五年省賽Java組真題“立方變自身”
下一篇：LeetCode刷題的一天（3）