2023.12.23力扣每日一题

发布时间:2023年12月25日

题目来源

力扣每日一题2023.12.23;题序:1962

我的题解

方法一 贪心思想+优先队列

首先很容易想到的就是使用贪心思想,也就是每次选择最大的石子堆进行移除。具体实现就是使用大根堆存储所有石子堆的大小,然后每次选择最大的石子堆进行移除。

时间复杂度:O(k×logn+n)。其中 n是数组 piles的长度。将数组变为优先队列消耗 O(n),k 次入队列和出队列的操作,每次消耗 O(log?n),总的时间复杂度是 O(k×log?n+n)。
空间复杂度:O(n)。优先队列所需的空间

public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a);
        int n=piles.length;
        for(int i=0;i<n;i++){
            pq.offer(piles[i]);
        }
        //选择石子堆进行移除
        while(!pq.isEmpty()&&k>0){
            int t=pq.poll();
            t=t-(int)Math.floor(t/2.0);
            if(t!=0)
                pq.offer(t);
            k--;
        }
        int res=0;
        while(!pq.isEmpty()){
            res+=pq.poll();
        }
        return res;
    }

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

文章来源:https://blog.csdn.net/weixin_42075274/article/details/135208888
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。