题目描述: 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例:
输入: [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]
讲解:
本题在LeetCode上是一道困难题. 其实乍一看思路很简单: 两层遍历, 外层窗口遍历 nums, 内层遍历窗口nums[i...i+k], 枚举出最大值放在ans中即可. 不过这样做时间复杂度就大致为 n * k 。提交的话不出意料是超时了。这时候我们来寻找优化的点, 本题提供的nums我们不方便操作(排序等); 从数学角度看我们也无法得到计算规律... 这时候只能从数据结构方面来寻找思路。
在一组数据中维护最大/小值, 我们可以找到一种非常合适的数据结构: 大/小根堆。我们可以使用Java中的PriorityQueue来完成此题。
不熟悉优先队列数据结构的话可以在菜鸟教程中先了解一下
优先队列: 特点是可以方便的维护最大/小值
优先队列pq中先放入nums中前k个元素, 此时nums中前k个(初始滑动窗口)中的最大值就是pq的第一个元素
滑动窗口右移, 那么优先队列pq中会新加入一个值(滑动窗口右侧第一个right)
pq中加入值right后, pq的的第一个元素就是右移后滑动窗口的最大值
滑动窗口右移后, 窗口会删去原先第一个值, 此时 pq中的一个值会对应的受到影响: 这里分为两种情况
- 当滑动窗口删去的值在pq中不为最大值时, 我们将其保留在pq中(不处理), 此时滑动后窗口的最大值为pq的第一个元素的值
- 当滑动窗口删去的值在pq中为最大值时, 我们将其删除, 得到新的最大值, 新的最大值有可能是1中保留在pq中未处理的值, 我们仍然需要删除它. 重复得到新的最大值--直到新的最大值存在于滑动窗口中
如何判断pq中的元素是否存在于滑动窗口中呢? 使用nums的下标标记一下, 也就是说在pq中存储二元组就行。
最后献上代码:
public class SlidingWindowMax {
public static int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
PriorityQueue pq = new PriorityQueue<>((a, b) -> b[0] - a[0]); // 最大堆
for (int i = 0; i < n; i++) {
pq.offer(new int[]{nums[i], i}); // 存储元素及其索引
// 确保窗口内的元素
while (pq.peek()[1] <= i - k) {
pq.poll();
}
// 当窗口大小到达k时，保存当前最大值
if (i >= k - 1) {
result[i - k + 1] = pq.peek()[0];
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] maxValues = maxSlidingWindow(nums, k);
System.out.println(Arrays.toString(maxValues)); // 输出：[3, 3, 5, 5, 6, 7]
}
}
Comments NOTHING