本文已收录至 Github《小白学算法》系列:https://github.com/vipstone/algorithm
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7]
LeetCode:https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[0];
// 最终结果数组
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < res.length; i++) {
// 初始化最大值
int max = nums[i];
// 循环 k-1 次找最大值
for (int j = i + 1; j < (i + k); j++) {
max = (nums[j] > max) ? nums[j] : max;
}
res[i] = max;
}
return res;
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[0];
// 最终结果数组
int[] res = new int[nums.length - k + 1];
// 存储的数据为元素的下标
ArrayDeque<Integer> deque = new ArrayDeque();
for (int i = 0; i < nums.length; i++) {
// 1.移除左边超过滑动窗口的下标
if (i >= k && (i - k) >= deque.peek()) deque.removeFirst();
// 2.从最后面开始移除小于 nums[i] 的元素
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
deque.removeLast();
// 3.下标加入队列
deque.offer(i);
// 4.将最大值加入数组
int rindex = i - k + 1;
if (rindex >= 0) {
res[rindex] = nums[deque.peek()];
}
}
return res;
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[]{};
// 最终结果数组
int[] res = new int[nums.length - k + 1];
// 优先队列
PriorityQueue<Integer> queue = new PriorityQueue(res.length, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
// 倒序排列(从大到小,默认是从小到大)
return i2 - i1;
}
});
// 第一轮元素添加
for (int i = 0; i < k; i++) {
queue.offer(nums[i]);
}
res[0] = queue.peek();
int last = nums[0]; // 每轮要移除的元素
for (int i = k; i < nums.length; i++) {
// 移除滑动窗口之外的元素
queue.remove(last);
// 添加新元素
queue.offer(nums[i]);
// 存入最大值
res[i - k + 1] = queue.peek();
// 记录每轮要移除的元素(滑动窗口最左边的元素)
last = nums[i - k + 1];
}
return res;
}
}
PS:从上面的执行结果可以看出,使用优先队列的执行效率很低,这是因为每次插入和删除都需要重新维护最大堆的元素顺序,因此整个执行的效率就会很低。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[]{};
// 最终结果数组
int[] res = new int[nums.length - k + 1];
// 优先队列
PriorityQueue<Integer> queue = new PriorityQueue(res.length, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
// 倒序排列(从大到小,默认是从小到大)
return i2 - i1;
}
});
// 第一轮元素添加
for (int i = 0; i < k; i++) {
queue.offer(nums[i]);
}
res[0] = queue.peek();
int last = nums[0]; // 每轮要移除的元素
for (int i = k; i < nums.length; i++) {
// 移除滑动窗口之外的元素
queue.remove(last);
// 添加新元素
queue.offer(nums[i]);
// 存入最大值
res[i - k + 1] = queue.peek();
// 记录每轮要移除的元素(滑动窗口最左边的元素)
last = nums[i - k + 1];
}
return res;
}
}
从上述结果可以看出,双端队列相比于优先级队列来说,因为无需重新计算并维护元素的位置,所以执行效率还是挺高的。
福 利
CSDN旗下公众号全新搜索技能上线啦!
只要在公众号内回复消息
就能自动回复想搜索的内容啦!
现在体验有惊喜,每日参与搜索打卡,
连续打卡满3天、7天、14天
均有CSDN精美礼品相送 百分百有礼!快戳
更多精彩推荐
☞倪光南、求伯君“出山”:爱解 Bug、无惧“35岁魔咒”、编码之路痛并快乐!
☞饿了么技术往事点分享 点点赞 点在看