LeetCode:239. 滑动窗口最大值

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 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]

分析：使用单调队列，每次在栈头保证是k个数中最大的元素就行。

class MyQueue_max {Deque<Integer> deque=new LinkedList();//删除元素，如果要删除的元素与队头的元素相等的话就要删除void poll(int val){//删除的元素只有队头那一个节点，所以只用判断一次就可以了if (!deque.isEmpty() && val == deque.peek()){deque.poll();}}//添加元素void add(int val){//如果要添加的元素大于队尾的元素的话，就需要将队尾元素删除，保证是单调递减的队列//这里是用while,因为是循环的判断队尾元素和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;//返回结果的长度；int[] res= new int[len];int count=0;//定于用于计数的countMyQueue_max queue_max = new MyQueue_max();for (int i=0;i < k;i++){//先将前k个加入到队列中去；保持k也是单调递减的队列queue_max.add(nums[i]);}res[count++]=queue_max.peek();//第一个k数中，队头是最大的元素；//遍历后面的数组for (int i=k;i< nums.length;i++){//判断移除的元素是不是最大的那个元素是k个数中的第一个数，是不是要移除它了queue_max.poll(nums[i-k]);//将后面的元素加入；queue_max.add(nums[i]);//将这次的k个数中最大的元素加入到res中；res[count++]=queue_max.peek();}return res;}
}