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

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]

示例3：

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

示例4：

输入：nums = [9,11], k = 2
输出：[11]

示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

提示：

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

Java解法

思路：

• 题目内容比较好理解，就是滑动数组在滚动时返回每次滚动窗口内的最大值

• 初步设想：开始滚动时，维护当前窗口大小的一个数组，有序记录最大值，在滚动时对移除值及移入值进行一个大小维护替换

  • 大小维护：对有序 数组二分查找更新
  • 设想更新：对当前窗口的大小数据构建一个大堆维护，当最大值移除时

• 设想2：找到当前滑动窗口最大值，在滚动超出当前滑动窗口之前，最大值都不会变（在没有移入更大值之前）

  • 在移除当前窗口最大值时，重新查找最大值

  • 能够完成但效率低，超时

    public static int[] maxSlidingWindow(int[] nums, int k) {
        //从0开始移动
        int maxIndex = findMaxIndex(nums, 0, k);
        int length = nums.length;
        int moveStep = length - k+1;
        int[] maxNums = new int[moveStep];
        maxNums[0] = nums[maxIndex];
        for (int i = 1; i < moveStep; i++) {
            //移入的值为 i+k-1
            maxIndex = nums[maxIndex]>nums[i+k-1]?maxIndex:i+k-1;
            if (i>maxIndex) {
                maxIndex = findMaxIndex(nums,i,k+i);
            }
            maxNums[i] = nums[maxIndex];
        }
    
        return maxNums;
    }
    
    
    public static int findMaxIndex(int[] nums, int start, int end) {
        int max = start;
        for (int i = start+1; i < end; i++) {
            max = nums[i]>=nums[max]?  i:max;//因为向右移动，所有相等时取index更大的值可以减少计算步骤
        }
        return max;
    }
    

• 参考官方解：单调队列

  • 算是对我的方法的优化吧，元素 n-1与n 如果nums[n-1]<nums[n]，那n-1在窗口中时，最大值一定不会为它
  • 按照这个性质来进行队列的维护

package sj.shimmer.algorithm.m4_2021;

import java.util.Deque;
import java.util.LinkedList;

import sj.shimmer.algorithm.Utils;

/**
 * Created by SJ on 2021/4/23.
 */

class D86 {
    public static void main(String[] args) {
        Utils.logArray(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3));
        Utils.logArray(maxSlidingWindow(new int[]{1},1));
        Utils.logArray(maxSlidingWindow(new int[]{1,-1},1));
        Utils.logArray(maxSlidingWindow(new int[]{9,11},2));
        Utils.logArray(maxSlidingWindow(new int[]{4,-2},2));
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            //双端队列存储前k个元素的可永久移除的数据，严格的单调递减
            Deque<Integer> deque = new LinkedList<Integer>();
            for (int i = 0; i < k; ++i) {
                while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }

            int[] ans = new int[n - k + 1];
            ans[0] = nums[deque.peekFirst()];
            for (int i = k; i < n; ++i) {
                while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
                while (deque.peekFirst() <= i - k) {
                    deque.pollFirst();
                }
                ans[i - k + 1] = nums[deque.peekFirst()];
            }
            return ans;
    }  
}

image

官方解

https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/

1. 优先队列

   我设想的解决方案，这里用大根堆来解决了维护问题

2. 单调队列

   参考方案：见上

3. 分块 + 预处理

   数学知识，