Daily LeetCode – day0109 1710. Maximum Units on a Truck

import java.util.PriorityQueue;

// 1710. Maximum Units on a Truck
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        PriorityQueue<BoxInformation> priorityQueue = new PriorityQueue<>((bi1, bi2) -> bi2.numberOfUnitsPerBox - bi1.numberOfUnitsPerBox);
        for (int[] boxType : boxTypes) {
            priorityQueue.offer(new BoxInformation(boxType[0], boxType[1]));
        }
        int ans = 0;
        while (truckSize > 0) {
            BoxInformation best = priorityQueue.poll();
            if (best == null) return ans;
            if (truckSize > best.numberOfBoxes) {
                ans += best.numberOfBoxes * best.numberOfUnitsPerBox;
            } else {
                ans += truckSize * best.numberOfUnitsPerBox;
            }
            truckSize -= best.numberOfBoxes;
        }
        return ans;
    }
}

class BoxInformation {
    Integer numberOfBoxes;
    Integer numberOfUnitsPerBox;

    public BoxInformation(Integer numberOfBoxes, Integer numberOfUnitsPerBox) {
        this.numberOfBoxes = numberOfBoxes;
        this.numberOfUnitsPerBox = numberOfUnitsPerBox;
    }
}
// 1710. Maximum Units on a Truck
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int len = boxTypes.length;
        Arrays.sort(boxTypes, (int[] bi1, int[] bi2) -> bi2[1] - bi1[1]);
        int ans = 0;
        int i = 0;
        while (truckSize > 0) {
            if (i < len) {
                if (truckSize > boxTypes[i][0]) {
                    ans += boxTypes[i][0] * boxTypes[i][1];
                } else {
                    ans += truckSize * boxTypes[i][1];
                }
                truckSize -= boxTypes[i][0];
                ++i;
            } else {
                return ans;
            }
        }
        return ans;
    }
}
学习笔记:
这是一道简单题,可以使用排序二维数组。
使用了了优先队列+创建对象,可能是因为放进去之后拿出来的概率太高了,所以花了10ms。
使用ArrayList+创建对象,需要13ms。
使用LinkedList+创建对象,需要23ms。可以看出LinkedList的排序属实性能不行。
最后写了一版二维数组排序的,只需要8ms。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注