BillyHao 
获赞
122
粉丝
1
关注
0
看过 TA
0
男 The Australian National University 2020 Java IP属地：未知暂未填写个人简介
2020-02-10 12:54
The Australian National University Java 
闭关修练：这个问题很大啊，答主使用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 
牛客675747613号：可以只开辟一个数组，原数组加两个指针分别从头、尾遍历0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了：