BillyHao level
获赞
122
粉丝
1
关注
0
看过 TA
0
男
The Australian National University
2020
Java
IP属地：未知
暂未填写个人简介
私信
关注
发布(5) 评论 刷题
2020-02-10 12:54
The Australian National University Java
用大顶堆实现滑动窗口最大值查询
import java.util.*; //思路：用一个大顶堆，保存当前滑动窗口中的数据。滑动窗口每次移动一格，就将前面一个数出堆，后面一个数入堆。 public class Solution { public PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>((o1,o2)->o2-o1);//大顶堆 public ArrayList<Integer> result = new ArrayList<Integer>();//保存结果 publi...
闭关修练：这个问题很大啊，答主使用PriorityQueue，慢慢分析一下。把窗口大小size记为k，实现初始将k个数入堆，时间O(k*log(k))，算常数时间。接着，开始遍历。从最大堆中取最大值为O(1)，借助调用remove(E e)方法来移出元素o，PriorityQueue中提供了三种remove方法，第一种为remove()，删除根元素，本质调用poll()方法，O(logk)。第二种提供索引，表示删除什么位置的元素remove(int i)，时间O(logk)。答主用了第三种remove(E e)，这需要先遍历数组找到删除元素的索引，从而时间复杂度O(k)。之后调用add(E e)，本质是调用offer(E e)，offer一个新元素，是通过把新元素放在末尾，然后将新元素不断往上与父母做比较得到，时间复杂度O(logk)。综上，时间复杂度为O(klogk + n(1 + k + logk)) = O(nk)，空间复杂度为O(1)，和直接暴力解法差别不大。
0 点赞 评论 收藏
分享
2020-01-06 09:36
The Australian National University Java
0 点赞 评论 收藏
分享
关注他的用户也关注了：
牛客网
牛客企业服务