贪心算法

简单

分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1，输入: g = [1,2,3], s = [1,1]，输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。

• 为了满足更多的小孩，就不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

• 这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

• 可以尝试使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

• 先遍历胃口，后遍历的饼干。如果是先遍历饼干，那么可能会出现饼干比胃口小，而满足不了其他小胃口的情况。

  

# 大饼干优先
class Solution:
    def findContentChildren(self, g, s):
        g.sort()  # 将孩子的贪心因子排序
        s.sort()  # 将饼干的尺寸排序
        index = len(s) - 1  # 饼干数组的下标，从最后一个饼干开始
        result = 0  # 满足孩子的数量
        for i in range(len(g)-1, -1, -1):  # 遍历胃口，从最后一个孩子开始
            if index >= 0 and s[index] >= g[i]:  # 遍历饼干
                result += 1
                index -= 1
        return result

# 小饼干优先
class Solution:
    def findContentChildren(self, g, s):
        g.sort()  # 将孩子的贪心因子排序
        s.sort()  # 将饼干的尺寸排序
        index = 0
        for i in range(len(s)):  # 遍历饼干
            if index < len(g) and g[index] <= s[i]:  # 如果当前孩子的贪心因子小于等于当前饼干尺寸
                index += 1  # 满足一个孩子，指向下一个孩子
        return index  # 返回满足的孩子数目

K 次取反后最大化的数组和

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）以这种方式修改数组后，返回数组可能的最大和。

示例，输入：A = [4,2,3], K = 1，输出：5，解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

• 贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
• 第二步：从前向后遍历，遇到负数将其变为正数，同时K–
• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
• 第四步：求和

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A

        for i in range(len(A)):  # 第二步：执行K次取反操作
            if A[i] < 0 and K > 0:
                A[i] *= -1
                K -= 1

        if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反
            A[-1] *= -1

        result = sum(A)  # 第四步：计算数组A的元素和
        return result

柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

输入：[5,5,5,10,20]，输出：true，解释：

1. 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。

2. 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。

3. 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。

4. 由于所有客户都得到了正确的找零，所以我们输出 true。

• 只需要维护三种金额的数量，5，10和20。有如下三种情况：

  • 情况一：账单是5，直接收下。
  • 情况二：账单是10，消耗一个5，增加一个10
  • 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

• 账单是20的情况，为什么要优先消耗一个10和一个5呢？因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

• 所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = 0
        ten = 0
        twenty = 0
        
        for bill in bills:
            # 情况一：收到5美元
            if bill == 5:
                five += 1
            
            # 情况二：收到10美元
            if bill == 10:
                if five <= 0:
                    return False
                ten += 1
                five -= 1
            
            # 情况三：收到20美元
            if bill == 20:
                # 先尝试使用10美元和5美元找零
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                    #twenty += 1
                # 如果无法使用10美元找零，则尝试使用三张5美元找零
                elif five >= 3:
                    five -= 3
                    #twenty += 1
                else:
                    return False
        
        return True

中等-序列问题

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1，输入: [1,7,4,9,2,5]，输出: 6，解释: 整个序列均为摆动序列。

示例 2，输入: [1,17,5,10,13,15,10,5,16,8]，输出: 7，解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

• 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

  

• 实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

• prediff =（nums[i] - nums[i-1]）, curdiff =（nums[i+1] - nums[i]）

• 需要考虑三种情况

  • 情况一：上下坡中有平坡

    

    它的摇摆序列长度是多少呢？ 其实是长度是 3，也就是我们在删除的时候 要不删除左面的三个 2，要不就删除右边的三个 2。这种情况下，可以删除左边的三个2，也可以删除右边的三个2。所以我们记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)

  • 情况二：数组首尾两端

    题目中说了，如果只有两个不同的元素，那摆动序列也是 2。因为我们在计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。这里我们可以写死，就是 如果只有两个元素，且元素不同，那么结果为 2。

    那么不写死的话，如何和我们的判断规则结合在一起呢？可以假设，数组最前面还有一个数字，那这个数字应该是什么呢？之前我们在 讨论 情况一：相同数字连续 的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0结果为 2。

    

    针对以上情形，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）。所以将 result 初始化为 1，这是为了解决只有两个元素的情况。

  • 情况三：单调坡度有平坡

    在版本一中，我们忽略了一种情况，即 如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]，如图

    

    版本一的代码在三个地方记录峰值，但其实结果因为是 2，因为 单调中的平坡 不能算峰值（即摆动）。之所以版本一会出问题，是因为我们实时更新了 prediff。那么我们应该什么时候更新 prediff 呢？我们只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。

• 本题异常情况的本质，就是要考虑平坡， 平坡分两种，一个是 上下中间有平坡，一个是单调有平坡

  

class Solution:
    def wiggleMaxLength(self, nums):
        if len(nums) <= 1:
            return len(nums)  # 如果数组长度为0或1，则返回数组长度
        curDiff = 0  # 当前一对元素的差值
        preDiff = 0  # 前一对元素的差值
        result = 1  # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值）
        for i in range(len(nums) - 1):
            curDiff = nums[i + 1] - nums[i]  # 计算下一个元素与当前元素的差值
            # 如果遇到一个峰值
            if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
                result += 1  # 峰值个数加1
                preDiff = curDiff  # 注意这里，只在摆动变化的时候更新preDiff
        return result  # 返回最长摆动子序列的长度

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)  # 如果数组长度为0或1，则返回数组长度
        #题目里nums长度大于等于1，当长度为1时，其实到不了for循环里去，所以不用考虑nums长度
        preDiff,curDiff ,result  = 0,0,1  
        for i in range(len(nums) - 1):
            curDiff = nums[i + 1] - nums[i]
            if curDiff * preDiff <= 0 and curDiff !=0:  #差值为0时，不算摆动
                result += 1
                #如果当前差值和上一个差值为一正一负时，才需要用当前差值替代上一个差值
                preDiff = curDiff  
        return result

单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1，输入: N = 10，输出: 9

示例 2，输入: N = 1234，输出: 1234

示例 3，输入: N = 332，输出: 299

• 例如 98，一旦出现 strNum[i - 1] > strNum[i] 的情况（非单调递增），首先想让 strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
• 以 332 举例，从后向前遍历332的数值变化为：332 -> 329 -> 299

贪心解法

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        # 将整数转换为字符串
        strNum = list(str(N))

        # 从右往左遍历字符串
        for i in range(len(strNum) - 1, 0, -1):
            # 如果当前字符比前一个字符小，说明需要修改前一个字符
            if strNum[i - 1] > strNum[i]:
                print(f"前一个元素 {strNum[i - 1]} 大于当前元素{strNum[i]}")
                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1
                # 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质
                print(f"此时数据变为: {strNum}")
                for j in range(i, len(strNum)):
                    strNum[j] = '9'
                print(f"填充 9 后为: {strNum}")

        # 将列表转换为字符串，并将字符串转换为整数并返回
        return int(''.join(strNum))


if __name__ == '__main__':
    s = Solution()
    r = s.monotoneIncreasingDigits(31490)
    print(r)
    
"""
前一个元素 9 大于当前元素0
此时数据变为: ['3', '1', '4', '8', '0']
填充 9 后为: ['3', '1', '4', '8', '9']
前一个元素 3 大于当前元素1
此时数据变为: ['2', '1', '4', '8', '9']
填充 9 后为: ['2', '9', '9', '9', '9']
29999
"""

暴力解法

class Solution:
    def checkNum(self, num):
        max_digit = 10
        while num:
            digit = num % 10
            if max_digit >= digit:
                max_digit = digit
            else:
                return False
            num //= 10
        return True

    def monotoneIncreasingDigits(self, N):
        for i in range(N, 0, -1):
            if self.checkNum(i):
                return i
        return 0

checkNum 方法接收一个整数 num，它的作用是检查 num 的每个数字是否按照递增的顺序排列。它通过不断地取出 num 的个位数字，并与一个变量 max_digit 比较，来判断当前数字是否小于等于之前遇到的最大数字。如果满足条件，则更新 max_digit 为当前数字，否则返回 False。最后，如果所有的数字都满足条件，即整个 num 是递增的，那么返回 True。

中等-股票问题

买卖股票最佳时机II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1，输入: [7,1,5,3,6,4]，输出:7，解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2，输入: [1,2,3,4,5]，输出: 4，解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

• 这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…..循环反复。如果想到其实最终利润是可以分解的，那么本题就很容易了

• 假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑

• 从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间
• 那么只收集正利润就是贪心所贪的地方！局部最优：收集每天的正利润，全局最优：求得最大利润。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(1, len(prices)):
            result += max(prices[i] - prices[i - 1], 0)
        return result

有难度-区间问题

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1，输入: [2,3,1,1,4]，输出: true，解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2，输入: [3,2,1,0,4]，输出: false，解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

• 当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？其实跳几步无所谓，关键在于可跳的覆盖范围。
• 不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。这个范围内，别管是怎么跳的，反正一定可以跳过来。
• 那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
• 每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

• i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。如果 cover 大于等于了终点下标，直接 return true 就可以了

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        if len(nums) == 1: return True
        i = 0
        # python不支持动态修改for循环中变量,使用while循环代替
        while i <= cover:
            cover = max(i + nums[i], cover)
            if cover >= len(nums) - 1: return True
            i += 1
        return False

跳跃游戏II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例，输入: [2,3,1,1,4]，输出: 2，解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。说明: 假设你总是可以到达数组的最后一个位置。

• 本题求解的是最少的跳跃次数，上题求解的是判断你是否能够到达最后一个位置
• 本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一
• 贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
• 不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数
• 所以这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖

class Solution:
    def jump(self, nums):
        if len(nums) == 1:
            return 0
        
        cur_distance = 0  # 当前覆盖最远距离下标
        ans = 0  # 记录走的最大步数
        next_distance = 0  # 下一步覆盖最远距离下标
        
        for i in range(len(nums)):
            next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖最远距离下标
            if i == cur_distance:  # 遇到当前覆盖最远距离下标
                ans += 1  # 需要走下一步
                cur_distance = next_distance  # 更新当前覆盖最远距离下标（相当于加油了）
                # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束
                if next_distance >= len(nums) - 1:  
                    break
        
        return ans

用最少数量的箭引爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1，输入：points = [[10,16],[2,8],[1,6],[7,12]]，输出：2，解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2，输入：points = [[1,2],[3,4],[5,6],[7,8]]，输出：4

• 局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
• 为了让气球尽可能的重叠，需要对数组进行排序。那么按照气球起始位置排序，还是按照气球终止位置排序呢？其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
• 如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points) == 0: return 0
        points.sort(key=lambda x: x[0])
        result = 1
        for i in range(1, len(points)):
            if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着，注意这里不是>=
                result += 1     
            else:
                points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界
        return result

无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1，输入: [ [1,2], [2,3], [3,4], [1,3] ]，输出: 1，解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2，输入: [ [1,2], [1,2], [1,2] ]，输出: 2，解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3，输入: [ [1,2], [2,3] ]，输出: 0，解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

• 这里也需要排序，是按照右边界排序，还是按照左边界排序呢？其实都可以。主要就是为了让区间尽可能的重叠。
• 下面图片按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了

区间，1，2，3，4，5，6都按照右边界排好序。当确定区间 1 和 区间2 重叠后，如何确定是否与 区间3 也重贴呢？就是取 区间1 和 区间2 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘了已经是按照右边界排序的了。区间4结束之后，再找到区间6，所以一共记录非交叉区间的个数是三个。总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。

"""
贪心 基于左边界
"""
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        # 按照左边界升序排序
        intervals.sort(key=lambda x: x[0])
        # 记录重叠区间数量
        count = 0  
        
        for i in range(1, len(intervals)):
        		# 存在重叠区间
            if intervals[i][0] < intervals[i - 1][1]:  
            		# 更新重叠区间的右边界
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  
                count += 1
        return count

      
"""
贪心 基于左边界 把452.用最少数量的箭引爆气球代码稍做修改
"""
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        # 按照左边界升序排序
        intervals.sort(key=lambda x: x[0])  
        # 不重叠区间数量，初始化为1，因为至少有一个不重叠的区间
        result = 1  
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= intervals[i - 1][1]:  
              	# 没有重叠
                result += 1
            else:  
              	# 重叠情况
                # 更新重叠区间的右边界
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  
        return len(intervals) - result

划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例，输入：S = “ababcbacadefegdehijhklij”，输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。提示，S的长度在[1, 500]之间。S只包含小写字母 ‘a’ 到 ‘z’ 。

• 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
• 可以分为如下两步：
  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occurrence = {}  # 存储每个字符最后出现的位置
        for i, ch in enumerate(s):
            last_occurrence[ch] = i

        result = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置
            if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间
                result.append(end - start + 1)
                start = i + 1

        return result

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1，输入: intervals = [[1,3],[2,6],[8,10],[15,18]]，输出: [[1,6],[8,10],[15,18]]，解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2，输入: intervals = [[1,4],[4,5]]，输出: [[1,5]]，解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

• 先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即 intervals[i] 的左边界 <= intervals[i - 1] 的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）

• 知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到 result 数组

class Solution:
    def merge(self, intervals):
        result = []
        if len(intervals) == 0:
            return result  # 区间集合为空直接返回

        intervals.sort(key=lambda x: x[0])  # 按照区间的左边界进行排序

        result.append(intervals[0])  # 第一个区间可以直接放入结果集中

        for i in range(1, len(intervals)):
            # 发现重叠区间
            if result[-1][1] >= intervals[i][0]:  
                # 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的
                result[-1][1] = max(result[-1][1], intervals[i][1])
            else:
                result.append(intervals[i])  # 区间不重叠

        return result

有难度-其余问题

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例，输入: [-2,1,-3,4,-1,2,1,-5,4]，输出: 6，解释: 连续子数组 [4,-1,2,1] 的和最大，为 6

• 如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方
• 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。全局最优：选取最大“连续和”。注意这里不是遇到负数就立刻丢弃，而是连续和为负数的时候，才从下一个元素重新计算。
• 局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
• 从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和

class Solution:
    def maxSubArray(self, nums):
        result = float('-inf')  # 初始化结果为负无穷大
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > result:  # 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count
            if count <= 0:  # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
                count = 0
        return result

加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

• 如果题目有解，该答案即为唯一答案。
• 输入数组均为非空数组，且长度相同。
• 输入数组中的元素均为非负数。

示例 1，输入，gas = [1,2,3,4,5]，cost = [3,4,5,1,2]

输出: 3 解释:

• 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
• 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
• 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
• 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
• 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
• 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
• 因此，3 可为起始索引。

方法1：

直接从全局进行贪心选择，情况如下：

• 情况一，如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
• 情况二，rest[i] = gas[i]-cost[i] 为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
• 情况三，如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

方法2：

• 首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的
• 每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

• 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置

方法1:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0  # 当前累计的剩余油量
        minFuel = float('inf')  # 从起点出发，油箱里的油量最小值
        
        for i in range(len(gas)):
            rest = gas[i] - cost[i]
            curSum += rest
            if curSum < minFuel:
                minFuel = curSum
        
        if curSum < 0:
            return -1  # 情况1：整个行程的总消耗大于总供给，无法完成一圈
        
        if minFuel >= 0:
            # 情况2：从起点出发到任何一个加油站时油箱的剩余油量都不会小于0，可以从起点出发完成一圈
            return 0  
        
        for i in range(len(gas) - 1, -1, -1):
            rest = gas[i] - cost[i]
            minFuel += rest
            if minFuel >= 0:
                # 情况3：找到一个位置使得从该位置出发油箱的剩余油量不会小于0，返回该位置的索引
                return i  
        
        return -1  # 无法完成一圈

方法2:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0  # 当前累计的剩余油量
        totalSum = 0  # 总剩余油量
        start = 0  # 起始位置
        
        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]
            
            if curSum < 0:  # 当前累计剩余油量curSum小于0
                start = i + 1  # 起始位置更新为i+1
                curSum = 0  # curSum重新从0开始累计
        
        if totalSum < 0:
            return -1  # 总剩余油量totalSum小于0，说明无法环绕一圈
        return start

监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

输入：[0,0,null,0,0]，输出：1，解释：如图所示，一台摄像头足以监控所有节点

输入：[0,0,null,0,null,0,null,null,0]，输出：2，解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

• 我们发现题目示例中的摄像头都没有放在叶子节点上！
• 摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
• 为什么不从头结点开始看起呢，为啥要从叶子节点看呢？因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
• 所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

• 此时这道题目还有两个难点，1. 二叉树的遍历，2. 如何隔两个节点放一个摄像头

  • 在二叉树中如何从低向上推导呢？可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。
  • 先来看看每个节点可能有几种状态，0：该节点无覆盖，1：本节点有摄像头，2：本节点有覆盖

• 因为在遍历树的过程中，就会遇到空节点，那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

• 看单层逻辑处理。主要有如下四类情况：

  • 情况1：左右节点都有覆盖。左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了

    

• 情况2：左右节点至少有一个无覆盖的情况，父节点就应该放摄像头

• 情况3：左右节点至少有一个有摄像头，那么其父节点就应该是2（覆盖的状态）

• 情况4：头结点没有覆盖，以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，所以递归结束之后，还要判断根节点，如果没有覆盖，result++

class Solution:
         # Greedy Algo:
        # 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优
        # 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head
        # 0: 该节点未覆盖
        # 1: 该节点有摄像头
        # 2: 该节点有覆盖
    def minCameraCover(self, root: TreeNode) -> int:
        # 定义递归函数
        result = [0]  # 用于记录摄像头的安装数量
        if self.traversal(root, result) == 0:
            result[0] += 1

        return result[0]

        
    def traversal(self, cur: TreeNode, result: List[int]) -> int:
        if not cur:
            return 2

        left = self.traversal(cur.left, result)
        right = self.traversal(cur.right, result)

        # 情况1: 左右节点都有覆盖
        if left == 2 and right == 2:
            return 0

        # 情况2:
        # left == 0 && right == 0 左右节点无覆盖
        # left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        # left == 0 && right == 1 左节点无覆盖，右节点有摄像头
        # left == 0 && right == 2 左节点无覆盖，右节点覆盖
        # left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if left == 0 or right == 0:
            result[0] += 1
            return 1

        # 情况3:
        # left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        # left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        # left == 1 && right == 1 左右节点都有摄像头
        if left == 1 or right == 1:
            return 2