LeetCode 239. Sliding Window Maximum

[Woodyiiiiiii]

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Follow up:
Could you solve it in linear time?

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

Constraints:

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

---

这道题是求k长度的滑动窗口内最大值的集合。
最简单的想法是暴力遍历，每次窗口移动都寻找当前窗口最大值存入结果数组中，时间复杂度为O(N*k)，虽然耗费时间，但也通过了测试：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len < k) return null;
        int[] res = new int[len - k + 1];
        int left = 0, right = k - 1;
        int max = Integer.MIN_VALUE, index = -1;
        int i = 0, j = 0;
        while (right < len) {
            max = Integer.MIN_VALUE;
            for (i = left; i <= right; ++i) {
                if (nums[i] > max) 
                    max = nums[i];
            }
            res[j++] = max;
            ++left;
            ++right;
        }
        return res;
    }
}

当然我们要继续优化。我们可以联想到TopK问题，其相关思路是维护一个优先队列，每次队列加入数值时队列都会根据自定义顺序排序，那么队列的头/尾就是我们要找的当前优先队列(即滑动窗口)的最大值，窗口移动时也要删除左边界数值：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len < k) return null;
        int[] res = new int[len - k + 1];
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        int i = 0, j = 0;
        for (i = 0; i < k; ++i)
            queue.add(nums[i]);
        res[j++] = queue.peek();
        int left = 1, right = k;
        while (right < len) {
            queue.remove(nums[left - 1]);
            queue.add(nums[right]);
            res[j++] = queue.peek();
            ++left;++right;
        }
        return res;
    }
}

然而这种做法有一个难以察觉的失误，当我们提交代码后会发现超时了，那么说明我们这个优先队列解法的时间复杂度同样是O(N*k)，这跟我们设想的不一样。

原因在于优先队列的remove函数是线性查找的，即时间复杂度为O(k)，我们查看优先队列源代码部分：

public boolean remove(Object o) {
  int i = indexOf(o);
  if (i == -1) {
    return false;
  } else {
    removeAt(i);
    return true;
  }
}

private int indexOf(Object o) {
  if (o != null) {
    final Object[] es = queue;
    for (int i = 0, n = size; i < n; i++) {
      if (o.equals(es[i])) return i;
    }
  }
  return -1;
}

所以这种做法跟暴力遍历的方法复杂度差不多，而且还多了O(k)的时间复杂度。

使用TreeMap可以实现堆的做法：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int n = nums.length;
        int len = n - k + 1;
        int[] res = new int[len];
        int idx = 0;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>((o1, o2) -> o2 - o1);
        int l = 0;
        int r = k - 1;

        // init
        int max = -10001;
        for (int i = l; i <= r; ++i) {
            max = Math.max(nums[i], max);
            treeMap.put(nums[i], treeMap.getOrDefault(nums[i], 0) + 1);
        }
        ++l;
        ++r;
        res[idx++] = max;

        // recursive
        while (r < n) {

            int dep = nums[l - 1];
            if (treeMap.containsKey(dep)) {
                treeMap.put(dep, treeMap.get(dep) - 1);
                if (treeMap.get(dep) == 0) {
                    treeMap.remove(dep);
                }
            }
            
            treeMap.put(nums[r], treeMap.getOrDefault(nums[r], 0) + 1);
            
            res[idx++] = treeMap.firstKey();
            ++l;
            ++r;

        }

        return res;
        
    }
}

优先队列的想法失败了，我们由滑动窗口的结构(两头都会进出数值)特点，可以联想到双端队列集合，那问题是我们该如何找出这个双端队列的最大值呢？

我们从双端队列的特点——头尾入手，定义该队列的头部必须是当前窗口内数值的最大值，这样我们就能获得结果了。如何实现？每次窗口移动，我们从队尾加入新增的数值，如果队尾数值小于它，那么抛出队尾数值，如此循环直到该新增数值找到它的位置，那些抛弃的数值并不重要，因为我们只要可能的最大值。当然，因为数值左边界移动，我们也要抛弃那些不在窗口内的数值，我们的队列保证了队头到队尾数值下标是递增顺序的，所以从队头抛出那些不应该在窗口内的数值就可以了。

最后还有一个问题，因为我们需要记录数值下标才能从队头抛出不在窗口的元素，而且保存元素下标的话我们可以获得元素本身和下标两个信息，而如果保存的是元素数值本身，我们只能获得一个信息，所以我们的双端队列应该保存的是数组下标，而不是元素本身。

这种队列内元素有序的叫单向队列。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n < k) return new int[0];
        int[] res = new int[n - k + 1];
        
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0, j = 0; i < n; ++i) {
            while (deque.size() > 0 && deque.peekFirst() < i - k + 1)
                deque.pollFirst();
            while (deque.size() > 0 && nums[deque.peekLast()] < nums[i])
                deque.pollLast();
            deque.offerLast(i);
            if (i - k + 1 >= 0) {
                res[j++] = nums[deque.peekFirst()];
            }
        }
        
        return res;
    }
}

使用双端队列实现这个不完整的“优先队列”的解法所用的时间复杂度是O(N)，因为对于双端队列来说从队头队尾操纵数据的时间复杂度为O(1)。

最后还有非常巧妙的分组+预处理解法，有些类似DP的解法。对数组进行k长度大小的分组，对每个分组内元素的下标i，我们预先求得以该下标结尾(后缀)的此k分组的最大值，和以该下标为开头(前缀)的此k分组的最大值；在遍历的时候，如果刚好窗口跟k分组重合，那prefix[i-k+1]和suffix[i]是相同的，如果跨了两个k分组，取suffix[i]和prefix[i-k+1]的最大值，所以公式是res[idx++] = Math.max(suffix[i], prefix[i + k - 1])，从而保证每次都能取得k窗口最大值：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int n = nums.length;
        int len = n - k + 1;
        int[] res = new int[len];
        
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        prefix[0] = nums[0];
        suffix[n - 1] = nums[n - 1];
        
        // pre manage
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefix[i] = nums[i];
            } else {
                prefix[i] = Math.max(prefix[i - 1], nums[i]);
            }
            int j = n - i - 1;
            if (j % k == (k - 1)) {
                suffix[j] = nums[j];
            } else {
                if (j == n - 1) {
                    continue;
                }
                suffix[j] = Math.max(suffix[j + 1], nums[j]);
            }
        }
        
        // for
        int idx = 0;
        for (int i = 0; i + k - 1 < n; ++i) {
            res[idx++] = Math.max(suffix[i], prefix[i + k - 1]);
        }
        
        return res;
        
    }
}

更让我佩服的是，竟然有非常简单的并且十分迅速的解题方法(1 ms & beat 100%)，解释都在代码上了，大概思路就是维护一个滑动窗口向右滑动，用变量maxPos记录最大值位置，每次移动分三种情况——①新加入的值大于最大值，则改变maxPos，计入结果数组；②新加入的值小于最大值，而且最大值仍是保持在窗口中，那么不作改变，计入结果数组；③其余情况说明新加入的值不是最大值而且最大值不在窗口中，所以需要重新遍历窗口寻找最大值。

这种解法的时间复杂度最好情况是O(N)，最坏情况是O(N*k)，并不稳定。其本质是在暴力法的基础上优化了一下，但有出乎意料的效果。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        int i, j;
        int maxPos = -1;

        for (i = 0; i <= nums.length - k; ++i) {
		    // Ending index of the current window
            j = i + k - 1;

            // new element >= max of last window
            // that means new element is max in the two windows
			// here using >= to make maxPos stay in the windows for a longer time
            if (maxPos != -1 && nums[j] >= nums[maxPos]) {
                maxPos = j;
                maxes[i] = nums[maxPos];
            }
            // new element < max of last window
            // AND the max of last window is also in this window
			// => it means the max of the last window is still the max of this window
            else if (i <= maxPos) {
                maxes[i] = nums[maxPos];
            }
            // new element < max of last window
            // AND the max of last window is not in this window
			// So we do not know which element is the max in this window, we have to scan the window to find it
            else {
                int maxWindow = Integer.MIN_VALUE;
                int maxPosWindow = 0;
                for (int z = i; z <= j; ++z) {
                    if (nums[z] > maxWindow) {
                        maxPosWindow = z;
                        maxWindow = nums[z];
                    }
                }
                maxPos = maxPosWindow;
                maxes[i] = nums[maxPos];
            }
        }
        return maxes;
    }
}

---

参考资料：

• https://leetcode.com/problems/sliding-window-maximum/
• https://leetcode.com/problems/sliding-window-maximum/discuss/458121/Java-All-Solutions-(B-F-PQ-Deque-DP)-with-Explanation-and-Complexity-Analysis
• https://leetcode.com/problems/sliding-window-maximum/discuss/437576/Java-1ms-solution-using-only-array-and-easy-to-understand
• 中文官网详细解法