239.?滑動窗口最大值

給你一個整數(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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

輸入：nums = [1], k = 1
輸出：[1]

分析：使用單調(diào)隊列，每次在棧頭保證是k個數(shù)中最大的元素就行。

class MyQueue_max {Deque<Integer> deque=new LinkedList();//刪除元素，如果要刪除的元素與隊頭的元素相等的話就要刪除void poll(int val){//刪除的元素只有隊頭那一個節(jié)點，所以只用判斷一次就可以了if (!deque.isEmpty() && val == deque.peek()){deque.poll();}}//添加元素void add(int val){//如果要添加的元素大于隊尾的元素的話，就需要將隊尾元素刪除，保證是單調(diào)遞減的隊列//這里是用while,因為是循環(huán)的判斷隊尾元素和val的值while (!deque.isEmpty() && val > deque.getLast()){deque.removeLast();}//如果不大于直接加入；deque.add(val);}//獲取棧頂元素int peek(){return deque.peek() ;}
}
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length == 1){return nums;}int len=nums.length - k + 1;//返回結(jié)果的長度；int[] res= new int[len];int count=0;//定于用于計數(shù)的countMyQueue_max queue_max = new MyQueue_max();for (int i=0;i < k;i++){//先將前k個加入到隊列中去；保持k也是單調(diào)遞減的隊列queue_max.add(nums[i]);}res[count++]=queue_max.peek();//第一個k數(shù)中，隊頭是最大的元素；//遍歷后面的數(shù)組for (int i=k;i< nums.length;i++){//判斷移除的元素是不是最大的那個元素是k個數(shù)中的第一個數(shù)，是不是要移除它了queue_max.poll(nums[i-k]);//將后面的元素加入；queue_max.add(nums[i]);//將這次的k個數(shù)中最大的元素加入到res中；res[count++]=queue_max.peek();}return res;}
}