LeetCode——1962. 移除石子使总数最小

通过万岁！！！

• 题目：给你一个数组。数组中的元素表示石子的个数，我们可以从里面移除一些元素，溢出的规则是第i位置的元素除2后向下取整。并且可以移除k次，要求最后的石子总个数最小。
• 思路一（超时）：一看题目基本就是贪心算法了，每次找最大的进行移除好了，但是关键问题就是移除完这一次以后，下一次怎么找到最大的元素。我最开始的思路是排序，移除完以后，对移除后的元素进行一次冒泡排序就好了。因为只需要对一个元素进行，所以时间复杂度是n，加上可以移动k次，所以时间复杂度是kn，但是这种方法超时了。
• 思路二：借助优先队列，也就是PriorityQueue。这个我最开始也想到了，但是确实不知道java中还有这个东西，也是百度了一下对应的api以后才写出来的代码。这个就比较简单了，存入PriorityQueue的元素会自动进行排序的。只需要遍历k次就好了。

java代码——超时

class Solution {
    public int minStoneSum(int[] piles, int k) {
        int sum = Arrays.stream(piles).sum();
        if (k == 0) {
            return sum;
        }
        Arrays.sort(piles);
        int lastIdx = piles.length - 1;
        int currIdx;
        for (int i = 0; i < k; i++) {
            int divRes = piles[lastIdx] / 2;
            piles[lastIdx] -= divRes;
            sum -= divRes;
            // 自己进行冒泡
            currIdx = lastIdx;
            while (currIdx - 1 >= 0 && piles[currIdx] < piles[currIdx - 1]) {
                // 交换currIdx和currIdx-1
                piles[currIdx] = piles[currIdx] + piles[currIdx - 1];
                piles[currIdx - 1] = piles[currIdx] - piles[currIdx - 1];
                piles[currIdx] = piles[currIdx] - piles[currIdx - 1];
                currIdx--;
            }
        }
        return sum;
    }
}

java代码——不超时

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);
        int sum = 0;
        for (int i = 0; i < piles.length; i++) {
            priorityQueue.offer(piles[i]);
            sum += piles[i];
        }
        for (int i = 0; i < k; i++) {
            Integer max = priorityQueue.poll();
            priorityQueue.offer(max - max / 2);
            sum -= max / 2;
        }
        return sum;
    }
}

• 总结：题目其实不难，但是这个api我个人掌握的确实还是不够的。其实我们数据结构中学到的数据结构，都在相应的语言中有对应的api的。