力扣 贪心算法题集 Python

准备蓝桥杯 ing，人菜没找到贪心算法的好课，无奈地用题海战术。记一下一些有价值的题吧

 将孩子的评分绘制成折线图，会发现折线由若干个峰构成，依据峰谷的位置进行划分

 对某个峰，用 up_len 表示递增部分长度，用 down_len 表示递减部分长度 (均不包括峰顶，但均包括峰谷)，如：up_len = 2，down_len = 3，则糖果分配是 [1, 2, 4, 3, 2, 1]

得某个峰对糖果的需求为：

这个方法在实现过程中要注意一些边界条件，最终代码如下：

class Solution(object):
    def candy(self, ratings):
        sum_ = 0
        # 记录总糖果数
        up_len = 0
        down_len = 0

        # 升序、降序部分长度
        def deng_cha(last):
            return (1 + last) * last // 2
            # 计算 1 + 2 + ... + last

        def feng_sum(up_len, down_len):
            return deng_cha(up_len) + deng_cha(down_len) + max([up_len, down_len]) + 1
            # 计算峰对糖果的需求

        for idx in range(1, len(ratings)):
            if ratings[idx] > ratings[idx - 1]:
                if down_len:
                    # 经过峰谷，即形成新的峰，结算上一个峰
                    sum_ += feng_sum(up_len, down_len) - 1
                    # 波谷是两个峰共享的，避免重复计算应 -1
                    up_len = 0
                    down_len = 0
                    # 置零升序、降序部分
                up_len += 1
                # 叠加升序部分
            elif ratings[idx] < ratings[idx - 1]:
                down_len += 1
                # 叠加降序部分
            else:
                sum_ += feng_sum(up_len, down_len)
                # 两评分相等时，第一个评分作为峰谷，第二个评分作为新峰的峰顶/峰谷
                up_len = 0
                down_len = 0
                # 置零升序、降序部分

        sum_ += feng_sum(up_len, down_len)
        # 未结算的峰
        return sum_

 照上面的样例讲一下思路：当处在 0 号加油站时，开往下一个加油站会使油量 -2 (由 1 - 3 得)，同理得各个加油站的前进开销为：[-2, -2, -2, 3, 3]

如果我们从 0 号加油站出发，则会在到 3 号加油站时，油量达到最低 -6 (见下图蓝色线)

如果把蓝线向上平移 6 个单位，即以 3 号加油站作为起点，则油量永远不会低于0 —— 所以前进开销累积的最小值处，就是起点。当然，前进开销累积到最后，是非负值才会有起点 (即总油量 >= 总消耗)

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        res = [g - c for g, c in zip(gas, cost)]
        min_ = res[0]
        min_idx = 0
        # 记录最小值的信息
        sum_ = res[0]
        for idx in range(1, len(res)):
            sum_ += res[idx]
            # 求和
            if sum_ < min_:
                min_ = sum_
                min_idx = idx
                # 比较取最小
        if sum_ < 0:
            return -1
        else:
            return (min_idx + 1) % len(res)

使用双指针，分别指向两端，保证容器的宽度最大。然后看两个指针对应的高度，哪个小就移动哪个，每次都计算一次，然后比较取最优

class Solution(object):
    def maxArea(self, height):
        left = 0
        right = len(height) - 1
        # 初始化双指针
        max_area = 0
        while left < right:
            max_area = max([max_area, (right - left) * min([height[left], height[right]])])
            # 和当前最优解比较
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return max_area

比方说现在给定的 prices = [1, 2, 3, 4]，最优的结果肯定是第一天买，最后一天卖出最好：4 - 1 = 3。当然这也等同于：- 1 + 2 - 2 + 3 - 3 + 4 = (- 1 + 2) + (- 2 + 3) + (- 3 + 4) = 3

所以说我们可以只扫描一次 prices，只要相邻两价格呈递增关系，就直接把差价算成利润

class Solution(object):
    def maxProfit(self, prices):
        profit = sum([(prices[idx] < prices[idx + 1]) * (prices[idx + 1] - prices[idx])
                      for idx in range(len(prices) - 1)])
        return profit