题目描述(困难难度)

输出每个窗口内的最大值。

解法一 暴力

两层 for 循环,每次都从窗口中找最大值即可。

public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n == 0) { return nums; } int result[] = new int[n - k + 1]; for (int i = 0; i < result.length; i++) { int max = Integer.MIN_VALUE; for (int j = 0; j < k; j++) { max = Math.max(max, nums[i + j]); } result[i] = max; } return result; } 

时间复杂度的话是 O(nk)

解法二优先队列

注意到我们每次循环都寻找最大的值,自然的可以想到优先队列,这样得到最大值就是 O(1) 了。

当优先队列的数字等于窗口大小的时候,我们只需要将第一个元素删除,然后将新的数字加入。

public int[] maxSlidingWindow(int[] nums, int k) { // 建立最大堆 Queue<Integer> max = new PriorityQueue<Integer>(new Comparator<Integer>() { @Override public int compare(Integer i1, Integer i2) { // TODO Auto-generated method stub return i2 - i1; } }); int n = nums.length; if (n == 0) { return nums; } int result[] = new int[n - k + 1]; int index = 0; for (int i = 0; i < n; i++) { //移除第一个元素 if (max.size() >= k) { max.remove(nums[i - k]); } max.offer(nums[i]); //更新 result if (i >= k - 1) { result[index++] = max.peek(); } } return result; } 

时间复杂度的话,循环中主要是调用了 remove 函数和 offer 函数,虽然 offer 函数的时间复杂度是 log 级的,但是 removeO(k) ,所以最终的时间复杂度依旧是 O(nk)

218 题 一样,我们可以用 TreeMap 代替优先队列,这样删除的时间复杂度也就是 log 级了。

public int[] maxSlidingWindow(int[] nums, int k) { TreeMap<Integer, Integer> treeMap = new TreeMap<>(new Comparator<Integer>() { @Override public int compare(Integer i1, Integer i2) { return i2 - i1; } }); int n = nums.length; if (n == 0) { return nums; } int result[] = new int[n - k + 1]; int index = 0; for (int i = 0; i < n; i++) { //此时不能用 treeMap 的大小和 k 比较, 因为 nums 中有相等的元素 //当 i >= k 的时候每次都需要删除一个元素 if (i >= k) { Integer v = treeMap.get(nums[i - k]); if (v == 1) { treeMap.remove(nums[i - k]); } else { treeMap.put(nums[i - k], v - 1); } } //添加元素 Integer v = treeMap.get(nums[i]); if (v == null) { treeMap.put(nums[i], 1); } else { treeMap.put(nums[i], v + 1); } //更新 result if (i >= k - 1) { result[index++] = treeMap.firstKey(); } } return result; } 

此时时间复杂度就是 O(nlog(k)) 了。

解法三 单调队列

参考 这里-solution-using-deque-with-explanation)。

我们可以用一个单调递减队列。单调递减队列添加元素的算法如下。

如果当前元素比队列的最后一个元素大,那么就将最后一个元素出队,重复这步直到当前元素小于队列的最后一个元素或者队列为空。进行下一步。

如果当前元素小于等于队列的最后一个元素或者队列为空,那么就直接将当前元素入队。

按照上边的方法添加元素,队列中的元素就刚好是一个单调递减的序列,而最大值就刚好是队头的元素。

当队列的元素等于窗口的大小的时候,由于添加元素的时候我们进行了出队操作,所以我们不能像解法二那样每次都删除第一个元素,需要先判断一下队头元素是否是我们要删除的元素。

public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> max = new ArrayDeque<>(); int n = nums.length; if (n == 0) { return nums; } int result[] = new int[n - k + 1]; int index = 0; for (int i = 0; i < n; i++) { if (i >= k) { if (max.peekFirst() == nums[i - k]) { max.removeFirst(); } } while (!max.isEmpty() && nums[i] > max.peekLast()) { max.removeLast(); } max.addLast(nums[i]); if (i >= k - 1) { result[index++] = max.peekFirst(); } } return result; } 

时间复杂度就是 O(n)了,因为每个元素最多只会添加到队列和从队列删除两次操作。

解法四

参考 这里-solution-in-Java-with-two-simple-pass-in-the-array) ,一种神奇的解法,有点 238 题 解法二的影子。

我们把数组 k 个一组进行分组。

nums = [1,3,-1,-3,5,3,6,7], and k = 3 | 1 3 -1 | -5 4 3 | 5 7 | 如果我们要求 result[1],也就是下边 i 到 j 范围内的数字的最大值 | 1 3 -1 | -5 4 3 | 5 7 | ^ ^ i j i 到 j 范围内的数字被分割线分成了两部分 

如果我们知道了左半部的最大值和右半部分的最大值,那么两个选最大的即可。

左半部分的最大值,也就是当前数到它右边界范围内的最大值。

rightMax[i] 保存 i 到它的右边界范围内的最大值,只需要从右到左遍历一遍就可以求出来了。

每次到右边界的时候就开始重新计算 max 值。

int rightMax[] = new int[n]; max = Integer.MIN_VALUE; for (int i = n - 1; i >= 0; i--) { if (max < nums[i]) { max = nums[i]; } rightMax[i] = Math.max(nums[i], max); if (i % k == 0) { max = Integer.MIN_VALUE; } } 

同理,右半部分的最大值,也就是当前数到它左边界范围内的最大值。

leftMax[i] 保存 i 到它的左边界范围内的最大值,只需要从左到右遍历一遍就可以求出来。

每次到左边界的时候就开始重新计算 max 值。

int leftMax[] = new int[n]; int max = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { if (i % k == 0) { max = Integer.MIN_VALUE; } if (max < nums[i]) { max = nums[i]; } leftMax[i] = Math.max(nums[i], max); } 

有了上边的两个数组,当前范围的两个边界 ijrightMax[i] 存储的就是左半部分(i 到右边界)的最大值,leftMax[j] 存储的就是右半部分(j 到左边界)的最大值。result[i] 的结果也就出来了。

result[i] = Math.max(rightMax[i], leftMax[j]); 

代码的话,把上边的部分结合起来即可。

public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n == 0) { return nums; } //当前数到自己的左边界的最大值 int leftMax[] = new int[n]; int max = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { if (i % k == 0) { max = Integer.MIN_VALUE; } if (max < nums[i]) { max = nums[i]; } leftMax[i] = Math.max(nums[i], max); } //当前数到自己的右边界的最大值 int rightMax[] = new int[n]; max = Integer.MIN_VALUE; for (int i = n - 1; i >= 0; i--) { if (max < nums[i]) { max = nums[i]; } rightMax[i] = Math.max(nums[i], max); if (i % k == 0) { max = Integer.MIN_VALUE; } } int result[] = new int[n - k + 1]; for (int i = 0; i < result.length; i++) { int j = i + k - 1; result[i] = Math.max(rightMax[i], leftMax[j]); } return result; } 

时间复杂度和解法三一样是 O(n)

解法一和解法二的话是正常的思路,一步一步水到渠成。

解法三的话直觉上其实也能意识到,我开始想到了单调栈,但一开始代码写错了,然后就换思路了,有点可惜,如果单调栈写对的话,应该可以写出解法三。

解法四的话就很厉害了,一般情况下很少往那方面想,不过这种将解分割的思想也是常用的。

results matching ""

    No results matching ""