239. 滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 时间复杂度：O(N)
        // 空间复杂度：O(N)
        // 双向队列
        int[] resArray = new int[nums.length - k + 1];
        // 定义双向队列，保存元素的索引
        // 每来一个元素，总要得到当前最大值，但是不是总固定保留 k 个元素，
        // 只把之前所有比当前元素小的那个数全部删掉
        // 队列每一论迭代只保留，从大到小、递减的一个队列
        // 更新原则为：保存 “ 更新更大 ” 的元素
        // 两个操作结合，队首可能需要删除、队尾可能需要添加
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        // 初始化
        for (int i = 0; i < k; i++) {
            // 如果队尾元素小于当前元素，直接删除
            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
        }
        resArray[0] = nums[deque.getFirst()];
        // 遍历数组所有元素，作为窗口的结束位置，
        for (int i = k; i < nums.length; i++) {
            // 判断，如果需要删掉的就是上一个窗口最大值，那么需要将队列中的最大值删掉
            // 因为窗口必须移动
            if (!deque.isEmpty() && deque.getFirst() == i - k) {
                deque.removeFirst();
            }
            // 判断新增元素是否可以删除队尾元素
            // 如果队尾小于当前元素，直接删除
            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
            // 保存结果
            resArray[i - k + 1] = nums[deque.getFirst()];
        }
        return resArray;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
// 时间复杂度：O(N)
        // 空间复杂度：O(N)
        int n = nums.length;
        // 定义结果数组
        int[] resArray = new int[n - k + 1];
        // 定义存放块内最大值的 left 和 right 数组
        int[] left = new int[n];
        int[] right = new int[n];
        // 左右扫描
        for (int i = 0; i < n; i++) {
            // 从左至右
            if (i % k == 0) {
                // 初始位置
                left[i] = nums[i];
            } else {
                // 不是起始位置，直接和 left[i-1] 比较取较大值
                left[i] = Math.max(left[i - 1], nums[i]);
            }
            // 从右至左
            int j = n - 1 - i;
            // 块中的最右边或者本身就是最右边元素
            if (j % k == k - 1 || j == n - 1) {
                // 初始位置
                right[j] = nums[j];
            } else {
                // 不是起始位置，直接和 right[j+1] 比较取较大值
                right[j] = Math.max(right[j + 1], nums[j]);
            }
        }
        // 再次扫描一次，对每个窗口取最大值
        for (int i = 0; i < n - k + 1; i++) {
            resArray[i] = Math.max(right[i], left[i + k - 1]);
        }
        return resArray;
    }
}

优先队列：

优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序。（顺序有两种形式：升序或者是降序） 比如我们往队列里面插入132，插入2的时候，就会在内部调整为123（默认顺序是升序）。正是由于这个优良特性可以帮助我们实现一系列问题。

针对降序，在新建优先队列时要：

               // 使用优先队列，实现大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

双向队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        // 保存索引
        ArrayDeque<Integer> deque = new ArrayDeque();
        // 第一轮
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.add(i);
        }
        res[0] = nums[deque.getFirst()];
        for (int i = k; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.getFirst() == i - k) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
            res[i - k + 1] = nums[deque.getFirst()];
        }
        return res;
    }
}

左右指针