[数据结构与算法]leetcode 239 滑动窗口最大值

思路

原题链接

1. 首先定义一个双端队列deque
2. 定义数组的长度len 和 一个结果数组res ，以及定义标志位idx
3. 开始for循环
4. 当数组为非空 并且 头结点的范围 不在 [i - k + 1, i] 内时，将队列头弹出 执行deque.peek()
5. 当队列非空，并且队列尾部索引对应数组元素的元素小于nums[i]的时候，将队列尾部弹出，执行deque.peekLast()
6. 将此时的i加入到deque中 执行deque.offer(i)
7. add() 和 offer()区别:
   add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断！
8. 当满足i >=k - 1的时候 将deque.peek()的索引对应的nums[i]的值加入到res数组中

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int len = nums.length;
        int[] res = new int[len - k + 1];
        int idx = 0;
        for(int i = 0; i < len; i++){
            while(!deque.isEmpty() && deque.peek() < i - k + 1) deque.poll();
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            deque.offer(i);
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}
//来自代码随想录的解释版本
//来自代码随想录的解释版本
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}