力扣(LeetCode)1710. 卡车上的最大单元数(C++)

贪心

排序+贪心。这和选最大面额的钞票是一类题。适合入门贪心，贪心的思想是步步最优，得到全局最优。最优策略是尽可能多的选装载的单元数量最大的箱子，然后选第二大，第三大，依次类推，直到装满卡车。

可以按装单元量给箱子从大到小排序，然后一次遍历所有箱子，即可得到答案。

代码展示

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(),boxTypes.end(),[](const vector<int> &a,vector<int> &b){
            return a[1]>b[1];//从大到小排序
        });
        int ans = 0;
        for(auto &x:boxTypes){
            if(truckSize<=x[0]){
                ans+=truckSize*x[1];
                truckSize=0;
                break;
            }else{
                ans+=x[0]*x[1];
                truckSize -= x[0];
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(nlogn)$， $n$ 是 $boxTypes$ 的长度。快排 $boxTypes$ 的时间复杂度是 $O(nlogn)$ ，一次遍历$boxTypes$ 的时间复杂度是 $O(n)$，总体时间复杂度 $O(nlogn+n)$ ，忽略较低数量级得到$O(nlogn)$。
2. 空间复杂度: $O(logn)$，快排的空间复杂度是 $O(logn)$ 。这是快排压栈的平均深度。