力扣-1710. 卡车上的最大单元数 & 1732. 找到最高海拔

题目描述

思路及实现

1710. 卡车上的最大单元数

首先要分清装载单元和装载数量，前者是箱子的容量，代表箱子可装载的单元数量，后者是卡车的容量，代表卡车可装载的箱子数量。
又由题目可以知道，每个类型箱子都有一定的数量和可装载单元数，对于每个箱子，重量是一致的（也就是说装载单元多并不会额外占用箱子数量），所以如果要找到卡车可以装载单元的最大总数，肯定是优先把装载单元数最大的箱子装上卡车。
为了降低时间复杂度，先对boxTypes进行排序，排序的依据就是boxTypes[i][1]，也就是箱子的容量，当然为了方便应该按照降序排列（即从大到小），排完序后边遍历边向卡车装箱子即可。

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        max_unit = 0
        boxTypes.sort(key=lambda i: i[1], reverse=True)
        for i in boxTypes:
            if i[0] > truckSize:  # 不能把当前这种类型的箱子全部装上去，那就把剩下的箱子容量装满开车走人
                max_unit += truckSize * i[1]
                break
            else:  # 能装下全部当前这种类型的箱子，装好后记得更新卡车剩余可装载箱子数
                max_unit += i[0] * i[1]
                truckSize -= i[0]
        return max_unit

1732. 找到最高海拔

其实一开始不是很看得懂题目想表达什么，看了一下示例就懂了，就是我们有altitude（海拔）列表，和gain（海拔差）列表，对于每个点的海拔，有altitude[i + 1] = altitude[i] + gain[i]，就这样，照着写就行了。

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitude = [0]
        for i, n in enumerate(gain):
            altitude.append(altitude[i] + n)
        return max(altitude)

当然可以进行优化，毕竟我们只需要前一海拔就能算出当前海拔，所以一个维护fore_altitude和max_altitude两个变量就可以了。

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        fore_altitude = 0
        max_altitude = 0
        for i in range(len(gain)):
            max_altitude = max(max_altitude, fore_altitude + gain[i])
            fore_altitude = fore_altitude + gain[i]
        return max_altitude

---

希望本文章能够帮到您~