滑动窗口与堆结合
2023-12-15 09:18:37
滑动窗口与堆结合
来自leetcode 239
第一种方法,直接在每次窗口移动后删除窗口前的元素,频繁删除引起堆化也会耗费时间。
/**
* 超时了,思考是因为堆中做了太多了remove导致堆化占了很多时间
* @param nums
* @param k
* @return
*/
public static int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Queue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);
int[] ans = new int[n - k + 1];
int t = 0;
int left = 0, right = k - 1;
for (int i = 0; i <= right; i++) {
pq.offer(nums[i]);
}
ans[t++] = pq.peek();
while (right < n - 1) {
pq.remove(nums[left++]);
pq.offer(nums[++right]);
ans[t++] = pq.peek();
}
return ans;
}
直接保存数字和索引,去优先队列的最大值之前,先对数字的索引做判断,不在窗口内的删除掉,这样会减少很多的删除。
/**
* 优先队列记录数和索引,减少重新堆化
* @param nums
* @param k
* @return
*/
public static int[] maxSlidingWindow2(int[] nums, int k) {
int n = nums.length;
Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1];
}
});
int[] ans = new int[n - k + 1];
int t = 0;
int left = 0, right = k - 1;
for (int i = 0; i <= right; i++) {
pq.offer(new int[]{nums[i], i});
}
ans[t++] = pq.peek()[0];
right = k;
while (right < n) {
pq.offer(new int[]{ nums[right], right});
while (pq.peek()[1] <= right - k) {
pq.poll();
}
ans[t++] = pq.peek()[0];
right++;
}
return ans;
}
文章来源:https://blog.csdn.net/weixin_45765073/article/details/134999030
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!