请选择 进入手机版 | 继续访问电脑版

1046. 最后一块石头的重量(Java)

[复制链接]
冰宇 发表于 2021-1-1 17:44:10 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
1046. 最后一块石头的重量

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块最重的石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x  b - a);        for (int stone : stones) {            pq.offer(stone);        }        while (pq.size() > 1) {            int a = pq.poll();            int b = pq.poll();            if (a > b) {                pq.offer(a - b);            }        }        return pq.isEmpty() ? 0 : pq.poll();    }}[/code] 时间复杂度:
时间复杂度:O(nlogn),此中 n 是石头数量。每次从队列中取出元素需要泯灭 O(logn) 的时间,即从大跟堆中取堆顶元素,最多共需要粉碎 n−1 次石头(即每次取出两块石头的巨细都不相等)。

来源:https://blog.csdn.net/weixin_43786147/article/details/111991889
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )