LeetCode_33_SlidingWindowMaximun

1. question: 滑动窗口最大值（困难）

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

2. answers

这道题没什么比较好的思路，先暴力破解一下，每次截取子数组，并取最大值。代码如下所示：

public class Solution_0030 {

    // 求解最大值
    public static int getMax(List<Integer> nums) {

        int maxNum = nums.get(0);

        for(int i: nums) {

            if(i > maxNum) maxNum = i;
        }

        return maxNum;
    }

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

        // 如果k大于等于数组长度，那么就直接取数组最大值
        if(k >= nums.length) k = nums.length;

        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length - k + 1; i++) {

            // 截取对应的数组
            List<Integer> temp = new ArrayList<>();
            for(int j = i; j < i + k; j++) {
                temp.add(nums[j]);
            }

            // 求解最大值
            result[i] = getMax(temp);

        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println();

//        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] nums = {1};

        int[] result = maxSlidingWindow(nums, 3);

        for(int i: result) {
            System.out.println(i);
        }
    }
}

毫无疑问，超时。那么改进一下，其实在上面截取数组的时候，就可以直接求解最大值了，没必要再遍历求解最大值。代码如下所示：

public class Solution_0030_02 {

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

        // 如果k大于等于数组长度，那么就直接取数组最大值
        if(k >= nums.length) k = nums.length;

        int[] result = new int[nums.length - k + 1];

        int max;

        for (int i = 0; i < nums.length - k + 1; i++) {

            max = nums[i];
            for(int j = i; j < i + k; j++) {

                max = Math.max(nums[j], max);
            }

            result[i] = max;

        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println();

        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
//        int[] nums = {1};

        int[] result = maxSlidingWindow(nums, 3);

        for(int i: result) {
            System.out.println(i);
        }
    }
}

但是这样做，依然是超时，因为总是重复遍历相邻窗口之间重复的部分。参考其他博客，代码如下所示：

public class Solution_0030_03 {

    public static 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;
    }

    public static void main(String[] args) {

        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
//        int[] nums = {1};

        int[] result = maxSlidingWindow(nums, 3);

        for(int i: result) {
            System.out.println(i);
        }
    }
}

个人理解不是很充分，大致描述一下：

因为总是重复遍历相邻窗口的重复部分，因此，可用一个队列来保存这些数据，并且数据是单调的（这里为了方便，单调递减。）

注意，在形成第一个窗口之后，后续的窗口就是在此基础上，去掉开头的元素，新增一个末尾元素。

另外，其实没必要保存一个窗口全部的数据。因为当后续遇到比之前大的元素后，前面的元素没有存在的必要了，无论是当前窗口还是后续窗口，前面比后面元素小的元素，一定是没用的。

因此，在入队的时候，如果队列中的元素比即将要入队的元素小，那么就将其弹出。

另外，还要保证（这是前提，优先级比上面高），队列内的元素都属于同一个窗口范围内。

当达到窗口范围后，队列（出口）的元素就是当前窗口的最大值。

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。