从零学算法239

239.给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 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]

• 他人题解：提示的这么明显了，不用滑动窗口都说不过去了。我们先过一遍暴力解法，首先数组长度为 n 的话，窗口滑动过程是从 [i,j] 到 [i+1,j+1]，然后继续加 1 加 1。如果左端的 i 是固定的，也就是窗口滑动过程为 [i,j] 到 [i,j+1]，那么其实最大值 x 的获取就简单多了，要么是之前的最大值，要么就是新加进来的 nums[j+1]，所以 x(i,j+1) = max(x(i,j), nums[j+1]) 。问题就是现在 i 不固定，我们从 [i,j] 到 [i+1,j+1] 缺少的 nums[i] 可能就是之前的最大值，这也就导致我们每次都需要从新划分范围内重新遍历找出最大值。需要寻找 (n-k+1) 次，每次遍历 k 个数，时间复杂度几乎为 O(nk)，所以我们优化的点就在于怎样快速找到这个最大值。
• 好吧凭我自己是想不到，最终解法使用了双端队列，我们需要保证的有两点，第一点：队列中的数一定是属于窗口 [i,j] 中的数，第二点为了降低最大值的查询速度，也就是我们使用双端队列的原因，我们让队列中的值保持降序，这样每次存入我们最终的 ans 数组时，取首位元素存入即可。保证了这两点那就表示我们存入结果数组的数就和上面的例子1一样，每次存入的数在滑动窗口范围内，且是当前最大值。具体看代码。

•   public int[] maxSlidingWindow(int[] nums, int k) {
    	  // 无效情况先排除
        if(nums.length == 0 || k == 0)return new int[0];
        // 结果数组
        int[] ans = new int[nums.length - k + 1];
        // 杀手锏，双端队列
        Deque<Integer> deque = new LinkedList<>();
        // 窗口的设定也挺巧妙的，i,j 从 [1-k,0] 不断后移，
        // 第一次正经得到范围的时候就是 [0,k-1]
        // 在这之前我们就只是老老实实存进队列，处理队列
        for(int i=1-k,j=0; j<nums.length; i++,j++){
        	// 队列首存的是最大值，如果窗口已经形成，并且在滑动过程中排除这个数了
        	// 那队列当然也要移除这个数，也就是我们要保证的第一点
            if(i>0 && nums[i-1] == deque.getFirst())deque.removeFirst();
            // 为了保持降序，移除之前的元素，为什么不会对我们最终结果造成影响
            // 因为我们给 nums[j] 腾位置，因此去掉的数最后都是无用的，
            // 这里去掉无用的数，加上上面的去掉队列的数
            // 两相结合保证了我们的第一点
            // 而无用的原因就是，nums[j] 在我们当前合法范围内(即 [i,j])，
            // 并且他最大的话我们就只用得上它，用不上去掉的数，这也就是我们保证的第二点
            // 或者引用他人的一句话：当一个元素进入队列的时候，它前面所有比它小的元素就不会再对答案产生影响
            while(!deque.isEmpty() && deque.getLast() < nums[j])deque.removeLast();
            // 位置腾好了，放心加进队列即可，保管你是保持降序的
            deque.addLast(nums[j]);
            // i==0 说明第一次到了正经范围了 [0,k-1]，也就是窗口终于形成了
            // 因此可以开始计算结果了
            if(i>=0)ans[i] = deque.getFirst();
        }
        return ans;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30

• 当然窗口形成也可以拆分成两部分，形成前后，这样虽然代码更长，但是逻辑更清晰且去掉了冗余的判断

•   public int[] maxAltitude(int[] heights, int limit) {
        if(heights.length == 0 || limit == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[heights.length - limit + 1];
        // 未形成窗口
        for(int i = 0; i < limit; i++) {
            while(!deque.isEmpty() && deque.peekLast() < heights[i])
                deque.removeLast();
            deque.addLast(heights[i]);
        }
        // 别忘了窗口已经形成了，可以记录一次结果了
        res[0] = deque.peekFirst();
        // 形成窗口后，也就不需要判断之前的 i>0,i>=0 了
        for(int i = limit; i < heights.length; i++) {
            if(deque.peekFirst() == heights[i - limit])
                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < heights[i])
                deque.removeLast();
            deque.addLast(heights[i]);
            res[i - limit + 1] = deque.peekFirst();
        }
        return res;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23