【栈和队列专题】—— 滑动窗口

双端队列

1.双端队列的概念：
普通队列是可以队首删除元素，队尾添加元素。对于双端队列，在队首、队尾都可以进行入队和出队的操作。

• 在一端进行出队和入队的操作，就有点类似栈的意思了，后入先出
• 也存在受限的双端队列：
  一端可以入队、出队操作，另一端只能进行入队操作；
  一端可以入队、出队操作，另一端只能进行出队操作。

2.双端队列的基本操作：

queue.peek() == queue.peekFirst() 查看队首元素
queue.peekLast() 查看队尾元素
queue.add() == queue.addFirst() 从队首添加元素
queue.addLast() 从队尾添加元素
queue.poll() == queue.pollFirst() 删除队首元素
queue.pollLast() 删除队尾元素

---

LeetCode 239: 滑动窗口最大值

️ 解题思路：

（1）创建一个结果集数组，大小为nums.length - k + 1

（2）创建一个双端队列，保存放到队列中的元素的索引。

如果队列为空，那么直接将元素索引进入队列；如果队列不为空，而且新进入的元素比上一个元素大，那么弹出上一个元素，再将当前元素入队
因为当前窗口中的最大值肯定不能是比当前待进入元素小的值

（3）判断当前最大值是否还在滑动窗口中，如果已经不再窗口中了，要将这个元素的索引从队首弹出

（4）将窗口中的最大值保存到结果集数组中

️ 代码部分：

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    

        //特殊情况处理
        if(nums == null || nums.length < 2){
    
            return nums;
        }
        //结果集数组
        int [] res = new int [nums.length - k + 1];
        //用双端队列来保存数组索引
        LinkedList<Integer> queue = new LinkedList();

        //遍历数组
        for(int i = 0; i < nums.length; i++){
    
            //如果队列不为空，当前对内元素小于下一个入队的元素，那么弹出队内的元素
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
    
                queue.pollLast();
            }

            //将当前元素的索引入队
            queue.addLast(i);

            //判断队列中的值是否有效
            if(queue.peek() <= i - k){
    
                queue.poll();
            }

            //将滑块中的最大值保存到结果集中,主要控制好第一个录入的元素即可
            if(i + 1 >= k){
    
                res[i - k + 1] = nums[queue.peek()];
            }
        }
        return res;
    }
}