leetcode刷题：栈与队列07（滑动窗口最大值）

239. 滑动窗口最大值

力扣题目链接

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

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

进阶：

你能在线性时间复杂度内解决此题吗？

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

一路做完磕磕绊绊的。
本来拿到这题，好像不难啊，就这还困难？？？

咔咔几行写完代码

    public int[] maxSlidingWindow(int[] nums, int k) {
    
        /** * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 * 输出：[3,3,5,5,6,7] * 共 8 个数，三个一组滑动，可组成 8-3+1 组，即 6 组 */
        if (nums.length < 2) {
    
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
    
            int max = -10000;
            for (int j = i; j < i + k; j++) {
    
                if (nums[j] > max) {
    
                    max = nums[j];
                }
            }
            result[i] = max;
        }
        return result;
    }

对此我只能说：好长的测试用例啊。。。
然后改进思路，把暴力破解改成滑动。把一个窗口分成以下几个部分。

left 是当前过期的最大值
right 是新进来的值
mid 是上一个最大值，是那个旧区间的最大值，如图所示：当前mid=3
每次窗口后移，先看看之前的最大值还能用吧（最大值是否和 left 的值相同，相同则不能用了，就得重新遍历窗口找最大值）；如果能用就继续用。

   public int[] maxSlidingWindow(int[] nums, int k) {
    
        if (nums.length < 2) {
    
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        /** * 如果当前范围元素的最大值仍然是下一个范围的最大值，则继续用。 * 此处要判断当前位置是否过了 */
        int maxValue = -10000;
        for (int j = 0; j < k; j++) {
    
            if (nums[j] > maxValue) {
    
                maxValue = nums[j];
            }
        }
        result[0] = maxValue;
        //前k个已经比较过了
        int resIndex = 1;
        //抽象出来，左边界值，中间部分最大值，右边界值
        for (int i = k; i < nums.length; i++) {
    
            //刚过期的左边界
            int left = nums[i - k];
            int mid = maxValue;
            int right = nums[i];

            if (left>mid-1) {
    
                //如果过期，就得重新再找最大值
                    maxValue = -10000;
                for (int j = i - k + 1; j < i + 1; j++) {
    
                    if (nums[j] > maxValue) {
    
                        maxValue = nums[j];
                    }
                }
            }

            //如果新元素比原来的大
            if (right >= mid) {
    
                maxValue = right;
            }
            result[resIndex] = maxValue;
            resIndex++;
        }
        return result;
    }

emmmm有长进，这次通过49个，只剩最后两个了。苦思冥想后，终于让我看到不一样的了。

这么多一样的。为了提高效率，除了要证明最大值是和 left 的值相同，更新证明这个最大值就是刚刚被淘汰的 left 的最大值。于是改了一行代码。通过了。

   public static int[] maxSlidingWindow2(int[] nums, int k) {
    
        /** * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 * 输出：[3,3,5,5,6,7] * 共 8 个数，三个一组滑动，可组成 8-3+1 组，即 6 组 */
        if (nums.length < 2) {
    
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        /** * 如果当前范围元素的最大值仍然是下一个范围的最大值，则继续用。 * 此处要判断当前位置是否过了 */
        int maxValue = -10000;
        for (int j = 0; j < k; j++) {
    
            if (nums[j] > maxValue) {
    
                maxValue = nums[j];
            }
        }
        result[0] = maxValue;
        //前k个已经比较过了
        int resIndex = 1;
        //抽象出来，左边界值，中间部分最大值，右边界值
        for (int i = k; i < nums.length; i++) {
    
            //刚过期的左边界
            int left = nums[i - k];
            int mid = maxValue;
            int right = nums[i];
            //部分优化，防止连续重复数字出现
            //如果left就是那个最大值
            if (left > mid - 1 && left != nums[i - k + 1]) {
    
                //如果过期，就得重新再找最大值
                maxValue = -10000;
                for (int j = i - k + 1; j < i + 1; j++) {
    
                    if (nums[j] > maxValue) {
    
                        maxValue = nums[j];
                    }
                }
            }

            //如果新元素比原来的大
            if (right >= mid) {
    
                maxValue = right;
            }
            result[resIndex] = maxValue;
            resIndex++;
        }
        return result;
    }

完美 AC !