hot100 239.滑动窗口最大值

思路：利用单调队列维护滑动窗口。

1.右边入（元素进入队尾，同时维护队列的单调性）。

2.左边出（元素离开队首）。

3.记录/维护答案（根据队首）。

为什么代码中的队首离开窗口写的是if而不是while？

答：

这是因为窗口在一步一步地向右滑动（像只蜗牛），所以元素也是一个一个地离开窗口，不会出现同一轮循环中有多个元素离开窗口的情况。

附代码：

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] res = new int[n - k + 1]; //窗口个数 LinkedList<Integer> queue = new LinkedList<>(); for(int i = 0;i < n;i++){ //1.右边入 while(!queue.isEmpty() && nums[queue.getLast()] < nums[i]){ queue.removeLast(); //移除所有比当前元素小的元素，确保队列中的元素是单调递减的 } queue.addLast(i); //注意保存的是下标，这样下面可以判断队首是否离开窗口 //2.左边出（移除过期元素） int left = i - k + 1; //窗口左端点 if(queue.getFirst() < left){ //队首元素已不在窗口中，移除过期的队首元素 queue.removeFirst(); } //3.在窗口的左端点处记录答案 if(left >= 0){ //由于队首到队尾单调递减，所以窗口的最大值就在队首 res[left] = nums[queue.getFirst()]; } } return res; } }