贪心算法

大纲

题目分类大纲：

什么是贪心算法？

贪心算法就是在每个阶段都选择局部最优解，从而达到全局最优。

贪心算法解题步骤

• 将问题分解为若干个子问题
• 找出合适的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

练习题

455、分发饼干

思路

遍历胃口和饼干列表，但是需要注意的是饼干列表不是每次都在移动，而是匹配了一个才会移动，因此这里不需要进行两层for循环，只需要一层for循环来遍历胃口列表即可。然后饼干列表可以使用一个指针index进行遍历，只有在能够进行匹配的情况下才需要将index进行移动。同时使用index来保存返回的结果。index可以直接用来当做最终的结果进行返回

利用贪心算法，每次都尽量喂饱胃口最大的，如果满足不了则往后移动判断能否满足下一个胃口最大的。

代码

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 先满足大胃口 | 此时胃口在移动
        g.sort(reverse=True)
        s.sort(reverse=True) # 从大到小
        index = 0
        for i in range(len(g)):
            if index<len(s) and s[index]>=g[i]:
                index+=1
        return index

本题不能先移动饼干，如果先移动饼干的话，就会出现下面的情况，导致最终没有满足条件的答案。

当然本题也可以先满足胃口小的，做法是类似的。但是如果是满足小胃口的话，就需要注意循环的顺序，这时候就是先遍历饼干，然后使用index对胃口列表进行遍历。

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        index = 0
        for i in range(len(s)):
            if index<len(g) and s[i]>=g[index]:
                index+=1
        return index

376、摆动序列(*)

计算峰值

prediff = nums[i] - nums[i-1]

curdiff = nums[i+1] - nums[i]

如果prediff>0 and curdiff < 0 或者 prediff < 0 and curdiff > 0，就需要统计波动

有三种特殊情况需要考虑：

• 情况一：上下坡中有平坡
• 情况二：数组首尾两端
• 情况三：单调坡中有平坡

情况一：上下坡中有平坡

可以统一规则，删除左边的3个2

情况二：数组首尾两端

如果数组中只包含两个元素，如果这两个元素不相同则摆动序列也为2

例如序列[2, 5]，如果靠统计差值计算峰值，需要有三个数才能进行统计，这时候，我们可以假定这个序列为[2,2,5]，这样preDiff=0 and curDiff=3，满足我们的条件，res+=1，就可以统一写法，不需要单独把len(nums)==2的情况单独拎出来了。

针对上述情况，我们可以假设res = 1，默认最右边有一个峰值

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums)<=1:
            return len(nums)
        res = 1
        curDiff = 0
        preDiff = 0
        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):
                res+=1
            preDiff = curDiff
        return res

这样的代码已经可以AC掉力扣中给出的测试用例，但是提交之后还是会有报错，这是因为这个代码忽略了情况三。

情况三：单调坡中有平坡

如果这时候的序列是[1, 2, 2, 2, 5]这样的，在上面的代码中得到的答案是3而不是2，这是因为程序的执行会按照情况一进行了。此时我们只需要进行的改动是只有在满足情况的条件下才会去修改preDiff指针。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums)<=1:
            return len(nums)
        res = 1
        curDiff = 0
        preDiff = 0
        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):
                res+=1
                preDiff = curDiff
        return res

53、最大子数组和（*）

初次尝试：

两层for循环进行遍历，计算所有子序列的和，碰到最大的就修改max_。这里需要注意max_在进行初始化的时候需要初始化为最小值float("-inf")

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_ = float("-inf")
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                # print(i,j)
                # print(nums[i:j+1])
                max_ = max(max_,sum(nums[i:j+1]))
        return max_

力扣中Python代码超时200/210

使用==贪心算法==

使用count进行和计算，如果碰到一个负数使得当前的count值小于0，则将count赋值为0重新进行子序列寻找，也设置一个max_初始化为最小值，当count>max_时，就进行更新。

注意：这里res = max(res, count) 这行代码需要在for循环的第二行（即需要在count添加之后），否则会报错。错误示例【[-1]】

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = float("-inf")
        count = 0
        for num in nums:
            count += num
            res = max(res, count)
            if count < 0:
                count = 0
        return res

动态规划

122、买卖股票的最佳时机II

题目中提到只能购买或者出售股票，并且最多持有一支股票。

只统计利润为正的即可得到最大收益。

贪心算法进行求解时，需要对利润进行拆解：以下面这个例子为例，我们只需要收集正利润的区间，就是股票买卖的区间。

贪心算法就体现在每天只取正利润的部分。

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

55、跳跃游戏

本题思路：通过查看当前结点能够跳跃的最远范围进行校验

这里nums中的元素所表示的含义是能够跳跃的最远范围，我们只需要判断其能够覆盖的范围，然后用其与len(nums)-1进行比较，如果大于等于则返回True，否则循环结束也无法到达最后一个下标的话，则返回False。

注意这里需要判断i的范围不能超过当前最远能够到达的区域，如果i超过了max_reach则直接break。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums)==1:
            return True
        max_reach = 0
        for i in range(len(nums)):
            if i > max_reach:
                return False
            max_reach = max(nums[i]+i, max_reach)
            if max_reach >= len(nums)-1:
                return True
        return False

在Python中无法动态修改for循环中的循环变量，可以改用while循环

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums)==1:
            return True
        i = 0
        reach = 0
        while i <= reach:
            reach = max(reach, nums[i]+i)
            if reach>=len(nums)-1:
                return True
            i += 1
        return False

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        res = 0  # 记录覆盖范围
        for i in range(n):
            if i > res:
                return False
            res = max(res, i + nums[i])
            if res >= n - 1:
                return True
        return False

Java代码：

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i <= nums.length; i++) {
            if (i > res) {
                return false;
            }
            res = Math.max(res, i + nums[i]);
            if (res >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

45、跳跃游戏II

【题目保证了肯定可以到达nums[i-1]】所以在到n-2这个下标位置的时候，其实已经就可以返回了

跳跃游戏中，需要我们判断是否能够到达最后一个下标，本题需要我们计算从第一个元素开始到最后一个下标的最小跳跃次数。

贪心的思路

• 局部最优
  • 当前尽可能走更多，如果还没到达终点，步数+1
• 整体最优
  • 一步尽可能走更多，从而达到步数最少

记录当前可以覆盖的最远距离和下一步可以覆盖的最远距离

遇到最远可以覆盖的范围，直接步数+1，

class Solution:
    def jump(self, nums: List[int]) -> int:
        cur_reach = 0 # 当前能够到达的最远距离
        next_reach = 0 # 下一步能够到达的最远距离
        res = 0 # 记录走的步数
        for i in range(len(nums)-1):
            next_reach = max(next_reach, nums[i]+i)
            if i == cur_reach:
                res +=1
                cur_reach = next_reach
                if next_reach>=len(nums)-1:
                    return res
        return res

• 时间复杂度O(n)
• 空间复杂度O(1)

注意这里的循环一定是len(nums)-1这个长度，这样可以避免nums = [0]的情况，否则会输出结果res=1的情况，但是实际上是无法到达的，应该输出为0

class Solution:
    def jump(self, nums: List[int]) -> int:
        cur_reach = 0
        next_reach = 0
        res = 0
        n = len(nums)
        for i in range(n-1):
            next_reach = max(next_reach, i + nums[i])
            if i == cur_reach:
                res += 1
                cur_reach = next_reach
                if next_reach >= n - 1:
                    return res
        return res

1005、K次取反后最大化数组和

局部最优解：让绝对值最大的负数变为正数，刚好可以利用Python中排序的key关键字，使用lambda表达式。如果。

如果数组内全部为正数，那么只需要将最小值也就是排序过后的数组中的最后一个元素在k为奇数的时候将其值修改为-1倍。

先按照绝对值大小进行排序，排序后再进行遍历的过程中寻找小于0且此时k大于0，然后将其值修改为-1倍，直到循环结束。如果循环结束之后k==1的话，就让nums中绝对值最小的数×(-1)

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x:abs(x),reverse=True)
        print(nums)
        for i in range(len(nums)):
            # 如果nums都大于0呢？？？ 都大于0 不进入循环
            if nums[i]<0 and k>0:
                nums[i]*=-1
                k-=1
            if k==0:
                return sum(nums)
        # 如果nums都大于0 只需要修改最小的那个值 修改其为负数即可
        # 如果k为偶数的话，也可以不修改
        if k%2==1:
            nums[-1] *= -1
        return sum(nums)

134、加油站（*）

暴力算法

暴力算法就是通过两层循环嵌套，外层循环表示从哪个加油站出发，内存循环进行判断是否能够绕一周回到当前位置，设置一个index表示当前所到达的加油站位置，经过内层循环如果能够绕一周到原来的位置，即index==i并且剩余的油量还大于等于0的话，返回当前外层循环的循环变量i。

这里index进行增加的时候因为是环形，类似于循环队列，需要除以len(gas)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 绕环路行驶一周
        # 模拟从各个加油站出发是否还能到达当前加油站
        mygas = 0
        # 从编号为i的加油站出发
        for i in range(len(gas)):
            mygas = gas[i]-cost[i] # 剩余的汽油
            index = (i+1)%len(gas)
            while mygas>=0 and index!=i:
                mygas += gas[index]
                mygas -= cost[index]
                index = (index+1)%len(gas)
            if mygas>=0 and index==i:
                return i
        return -1

算法分析

• 时间复杂度 O(n^2^)
• 空间复杂度 O(1)

暴力算法会超时

贪心算法（1）

分情况讨论：

• 情况1：如果gas总量小于cost总量，则无论从哪里出发都无法绕一圈回到起点
• 情况2：rest[i]=gas[i]-cost[i]为一天剩下的油，i从0开始累加到最后一个加油站， 如果累加没有出现负数，那么就从0开始，0号为起点
• 情况3：如果累加的值为负数，说明不是从0开始，从后向前，看哪个节点可以把这个负数填平，如果能把负数填平的节点就是出发点。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas)<sum(cost):
            return -1
        min_ = float("inf")
        rest = 0
        for i in range(len(gas)):
            rest+=gas[i]-cost[i]
            min_ = min(min_,rest)
        print(rest,min_)
        # 如果min_>=0 说明从0开始出发即可
        if min_>=0:
            return 0
        # 如果min_<0  说明需要从非0出发点出发
        for i in range(len(gas)-1,-1,-1):
            # ？
            rest = gas[i]-cost[i]
            min_ += rest
            if min_>=0:
                return i
        return -1

贪心算法2

首先判断gas总和是否小于cost，小于则直接返回-1

然后通过累加gas[i]-cost[i]，如果差值小于0，出发的起点一定不在[0,i]这个区间范围内，需要从i+1开始进行判断。同时如果计算到某个节点rest<0，还需要将rest置为0重新计算。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas)<sum(cost):
            return -1        
        start = 0
        rest = 0 # 用于计算差值的累加和
        for i in range(len(gas)):
            rest += gas[i]-cost[i]
            if rest < 0:
                # 下标要从i+1开始
                start = i+1
                rest = 0
        return start

• 时间复杂度O(n) 只有单层for循环
• 空间复杂度O(1)

135、分发糖果（*）

题目中说到相邻的两个孩子评分更高的孩子会获得更多的糖果，需要迭代的去进行比较，及时更新每一步。

这里需要注意，如果需要判断右孩子比左孩子大的话需要从前往后进行遍历，因为后面的值需要前面的结果。如果是判断左孩子比右孩子的大的话需要从后往前进行遍历，因为前面的结果需要依靠后面的结果进行累加。但是需要注意的是，有的结果已经已经比左边大了，同时有比右边大，这时候需要判断当前res[i]和res[i+1]+1哪个值更大就赋值为哪个值避免测试用例的错误。

出错的测试用例 ratings = [1,3,4,5,2]，错误的地方就在于在从后往前进行遍历的时候，ratings[3]>ratings[4]，res[3] = res[4]+1 = 2，但是2小于从左往右进行遍历的结果4，这里我们应该选择的是两者的最大值。因此这里使用res[i] = max(res[i],res[i+1]+1)进行赋值。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        res = [1]*len(ratings)
        # 从前向后 判断右孩子如果比左孩子大的话，就需要进行ratings[i] = ratings[i-1]+1
        for i in range(1,len(ratings)):
            if ratings[i]>ratings[i-1]:
                res[i] = res[i-1]+1
        # 从后向前 判断如果左孩子比右孩子大的话，就需要进行ratings[i] = ratings[i+1]+1
        for i in range(len(ratings)-2,-1,-1):
            if ratings[i]>ratings[i+1]:
                res[i] = max(res[i],res[i+1]+1)
        # print(res)
        return sum(res)

本题中用到了两次贪心算法

• 一次从前往后进行遍历的贪心算法
• 一次从后往前进行遍历的贪心算法

860、柠檬水找零

如果付款金额为20美元，优先找1张10美元1张5美元，如果没有才找3张5美元的。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        # 判断除了五美元以外的钞票是否能找开
        # from collections import defaultdict
        # myhash = defaultdict(int)
        myhash = {20:0, 10:0, 5:0}
        now = []
        for bill in bills:
            myhash[bill]+=1
            # 超过5块就进行找零
            # print(bill,myhash)
            if bill==10:
                if myhash[5]>0:
                    myhash[5]-=1
                else:
                    return False
            if bill==20:
                if (myhash[10]>0 and myhash[5]>0):
                    myhash[10]-=1
                    myhash[5]-=1
                elif myhash[5]>2:
                    myhash[5]-=3
                else:
                    return False
        return True

406、根据身高重建队列（*）

题目理解：

本题中需要注意的地方在于列表中的第二个元素是排在其前面总共有多少个人，矮个子排在高个子前面是没有影响的，但是高个子排在矮个子前面是有影响的。另外如果是身高一样的人，第二个数字越大的人排序越靠后，这是第一个排序的因素，第二个排序的因素是如果数字相同，身高越低的人越靠后。

两个维度进行比较的时候会顾此失彼，类似于分发糖果的题目！！！

先确定一个维度，贪心另一个维度

做法：

先按照身高逆序排序再按照前面有几个人正序排序。然后通过构建新的列表往其中按照第二个元素位置顺序添加元素来实现最终的答案。

[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

局部最优：优先按照身高people的k进行插入。插入操作后的people满足队列属性

全局最优：全部插入完成后，整个队列满足题目要求。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(x[0],-x[1]),reverse=True)
        # print(people)
        res = []
        for po in people:
            pos = po[1]
            res.insert(pos,po)
        return res

452、用最少数量的箭引爆气球

本题属于==区间问题==

思路如上，首先对points依据其第一个元素进行排序，得到[[1, 6], [2, 8], [7, 12], [10, 16]]的结果，然后列表进行遍历。遍历的过程中我们队右边界进行更新，每次更新最小的右边界。

• 如果左边界大于右边界
  • res = res + 1
• 左边界小于等于有边界
  • 更新当前的最小右边界

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # 判断是否有重叠的区间？
        points.sort(key=lambda x:(x[0],x[1]))
        # print(points)
        res = 1
        for i in range(1,len(points)):
            # 左边界大于右边界
            if points[i][0]>points[i-1][1]:
                res += 1
            else:
                # 更新最小右边界
                points[i][1] = min(points[i][1], points[i-1][1])
        return res

优化思路：

这个优化后的算法使用贪心策略，先将气球按右边界进行排序，然后遍历气球列表，如果发现当前气球的起始位置大于当前箭的结束位置，说明需要增加箭的数量，并更新箭的结束位置。这样可以有效减少时间复杂度，避免了多次合并区间的操作。

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0

        points.sort(key=lambda x: x[1])  # 按照气球的右边界进行排序
        arrows = 1
        end = points[0][1]

        for start, point_end in points:
            # 如果当前气球的起始位置大于当前箭的结束位置，则增加箭的数量，并更新箭的结束位置
            if start > end:
                arrows += 1
                end = point_end
        
        return arrows

435、无重叠区间

贪心算法基于左边界

首先对列表进行排序，然后对其进行循环遍历（从列表中的第二个元素开始，即下标为1），如果当前的左边界要小于前一个区间的右边界则说明发生重叠，将res+1，然后看当前结点的右边界是否大于上一个结点的右边界，如果大于则更新，如果小于则不进行操作。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        res = 0
        intervals.sort()
        for i in range(1,len(intervals)):
            if intervals[i][0]<intervals[i-1][1]:
                res+=1
                intervals[i][1] = min(intervals[i][1],intervals[i-1][1])
        return res

本题计算的是如果构造没有重叠区间的话，需要去掉几个区间。

上一题引爆气球是计算的最少需要多少个箭，本题中需要判断的不重叠的区间，只需要用总区间数减去射箭的次数即可。因为在气球爆炸问题中如果是相邻边界，则使用一支箭即可，但在本题中如果相邻不算重叠，所以本题如果采用上一题的思路则条件需要修改为>=，其余的做法都是一致的，修改最终返回值为len(intervals)-res

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        res = 1
        intervals.sort()
        for i in range(1,len(intervals)):
            if intervals[i][0]>=intervals[i-1][1]:
                res+=1
            else:
                # 更新右边界
                intervals[i][1] = min(intervals[i][1],intervals[i-1][1])
        return len(intervals)-res

763、划分字母区间（*）

右指针一直取所走过的最大的下标范围，如果当前循环变量的值刚好等于当前的最大右指针则将切割点加入res，切割点的值为right-left+1，同时更新left为i+1

本题难点就在于如何进行遍历过程中的right修改，用哈希表来存放下标并不难。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        myhash = defaultdict(int)
        for i in range(len(s)):
            myhash[s[i]] = i
        # print(myhash)
        res = []
        left = 0
        right = 0 # 右指针 结果是切割点
        for i in range(len(s)):
            right = max(right,myhash[s[i]])
            if right==i:
                res.append(right-left+1)
                left = i + 1
        return res

56、合并区间（*）

思路：首先对区间进行排序，然后对其进行比较

这里需要注意的是，比较res[-1]的时候，用其右边界和当前区间的左边界进行比较，比较的时候是>=，因为[1,2]和[2,3]区间是被视为重叠的区间的。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        # print(intervals)
        res = [intervals[0]]
        for i in range(1,len(intervals)):
            if res[-1][1]>=intervals[i][0]:
                # 合并
                res[-1][1] = max(intervals[i][1], res[-1][1])
            else:
                # 加入结果集
                res.append(intervals[i])
        return res

区间问题的复盘

1. 用最少数量的箭引爆气球
2. 无重叠区间
3. 划分字母区间
4. 合并区间

57、插入区间

738、单调递增的数字

暴力解法（超时）

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        def judge(num):
            # 判断一个数是否是递增的数
            nums = list(str(num))
            nums_sort = sorted(nums)
            # nums_set = list(set(nums))
            # print(nums,nums_sort)
            return nums==nums_sort
        res = 0
        for i in range(n,0,-1):
            if judge(i):
                res = i
                break
        return res

贪心算法

从后往前进行比较，另外每次修改后都需要将后面的数修改为9，避免类似100这样的问题

从后往前进行遍历 332–> 329 –> 299

从前往后比较会出现问题，例如332，从前往后比较332–>329，此时第二个2小于3了。

从前往后遍历使得后面修改导致数字并不是递增的，从后往前遍历就可以避免这个问题

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # num = list(str(n))
        nums = list(map(int,str(n)))
        # print(nums)
        for i in range(len(nums)-2,-1,-1):
            if nums[i]>nums[i+1]:
                # nums[i+1] = 9
                nums[i] -= 1
                for j in range(i+1,len(nums)):
                    nums[j] = 9
        # 如何快速把[1,2,3,4]合并成1234数字
        return int("".join(map(str,nums)))

968、监控二叉树(*)

思路：

贪心总结