经典算法思想之滑动窗口

滑动窗口

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: 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 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

分析：
数组的长度为n 窗口的大小为k 可形成的窗口个数 n-k+1

通过队列来记录最大值

窗口未形成的阶段
遍历数组，同时更新队列

窗口已形成的阶段
每次窗口移动，都是在头部移除元素，尾部增加元素
在窗口变化过程中 记录其最大值的变化 (让最大值一直出现在第一位)

让队列中已存在的元素 和新添加的元素比较 如果已存在的更小 那么覆盖
如果已存在的更大 新添加的元素是候选 缀到队列之后

滑动窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

窗口 max队列
[1 3 -1] [1] -> [3] -> [3,-1]
[3 -1 -3] [3,-1,-3]
[-1 -3 5] [-1,-3] -> [5]
[-3 5 3] [5,3]
[5 3 6] [6]
[3 6 7] [7]

public static int[] maxSlidingWindow(int[] nums, int k) {

        // 记录每个窗口的最大值   n-k+1为形成的窗口个数
        int[] result = new int[nums.length - k + 1];

        // 使用队列记录最大值的候选值
        Deque<Integer> deque = new ArrayDeque<>();

        // 窗口未形成的阶段
        for (int i = 0; i < k; i++) {
            print(deque);
            // 每次都取 队尾元素和新元素 比较  如果队尾更小  删除
            while (!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.pollLast();
            }
            deque.offerLast(nums[i]);
        }

        // 此时第一个窗口形成  deque的队头元素就是第一个窗口的最大值
        result[0] = deque.peekFirst();
        print(deque);

        // 窗口已形成的阶段
        for (int i = k; i < nums.length; i++) {
            System.out.println("-----第" + (i-k+1) + "次滑动");
            // 删了元素 nums[i-k]  添了元素 nums[i]
            if(nums[i-k] == deque.peekFirst()){
                // 如果删的是最大值  同时从deque移除
                deque.pollFirst();
            }

            // 新增
            while (!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.pollLast();
            }
            deque.offerLast(nums[i]);

            result[i-k+1] = deque.peekFirst();
            print(deque);
        }

        return result;
    }


    public static void print(Deque<Integer> deque){
        for (Integer integer : deque) {
            System.out.print(integer + " ");
        }
        System.out.println();
    }