代码随想录：贪心算法

2024-04-25 2025-04-08 约 5700 字预计阅读 12 分钟 - 次阅读 - 条评论

分发饼干

1
2
3
4
5
6
7
8
9


func main() {
    g := []int{1, 2}
    s := []int{1, 2, 3}
    r := findContentChildren(g, s)
    fmt.Println(r) // 2
}
func findContentChildren(g []int, s []int) int {
    // ......
}

答案

本题可以使用贪心算法。我们要获取尽量多的饼干和胃口匹配的数量，先将胃口数组g和饼干数组s进行排序，然后让大饼干尽量去匹配大胃口。

如果当前饼干不满足当前的胃口，则缩小胃口值（指针位置左移）。

双重循环遍历时，外层遍历的是胃口数组，因为我们要用饼干去匹配胃口，当匹配时，缩小胃口值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func findContentChildren(g []int, s []int) int {
    sort.Ints(g)        // 胃口
    sort.Ints(s)        // 饼干
    index := len(s) - 1 // 饼干的匹配位置
    count := 0          // 统计匹配的数量
    for i := len(g) - 1; i >= 0; i-- {
       if index >= 0 && s[index] >= g[i] { // 饼干大小匹配胃口大小
          count++
          index--
       }
    }
    return count
}

摆动序列

376. 摆动序列

较难，建议多加练习。

1
2
3
4
5
6
7
8


func main() {
    nums := []int{1, 7, 4, 9, 2, 5}
    r := wiggleMaxLength(nums)
    fmt.Println(r) // 6
}
func wiggleMaxLength(nums []int) int {
    // ......
}

答案

本题需要计算 nums 数组的最长摆子序列，计算要计算 nums 中有多少个峰值（局部最大和局部最小）。

可以考虑使用贪心算法，当 nums[i-1]-nums[i]<0 && nums[i+1]-nums[i]>0或者 nums[i-1]-nums[i]>0&&nums[i+1]-nums[i]<0（i 位置的左右差值一正一负数）时，就是我们需要统计的位置。

但我们还需要考虑出现平坡的情况，参考：0376.摆动序列。

如果左边 i 的左侧位置出现平坡（非单调平坡），那么我们只统计最后一个平坡的位置，也就是 nums[i-1]-nums[i]<=0 && nums[i+1]-nums[i]>0（添加了左边等于 0 的情况），或者 nums[i-1]-nums[i]>=0&&nums[i+1]-nums[i]<0（添加了左边等于 0 的情况）。

但还有可能出现单调平坡的情况，也就是差值先为正，然后出现部分 0，然后再继续为正，而不是负，这时候我们不应该统计这样的平坡。

在代码中，我们使用 preDiff 表示i前面的差值，postDiff 表示 i 后面的差值

我们可以在出现非单调平坡时，才更新 preDiff 的值为 postDiff（当出现了转折才更新），这样当出现单调平坡时，也不会被统计了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func wiggleMaxLength(nums []int) int {
    // 先处理nums长度为1和2的情况
    if len(nums) == 1 {
       return 1
    }
    if len(nums) == 2 {
       if nums[0] != nums[1] {
          return 2
       } else {
          return 1
       }
    }
    preDiff := 0
    postDiff := 0
    count := 1 // 最后一个位置是摆动的
    // nums的长度至少为3
    for i := 0; i < len(nums)-1; i++ { // 我们不遍历最后一个元素，认为最后一个位置一定是摆动的
       postDiff = nums[i+1] - nums[i]
       if (preDiff <= 0 && postDiff > 0) || (preDiff >= 0 && postDiff < 0) { // 左负右正 或 左正右负
          count++
          preDiff = postDiff // 只有当出现正反坡度变化时，才更新preDiff的值（为了解决单调平坡的问题）
       }
    }
    return count
}

最大子数组和

53. 最大子数组和

1
2
3
4
5
6
7
8


func main() {
    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    r := maxSubArray(nums)
    fmt.Println(r) // 6
}
func maxSubArray(nums []int) int {
    // ......
}

答案

本题使用贪心算法，需要明确我们“贪”的是哪里。

不是遇到负数就跳过该元素，而是：如果“连续和”为负数，我们就放弃当前得到的“连续和”，从下一个位置重新开始计算“连续和”，因为前面小于 0 的“连续和”只会拖累我们的计算，让我们得到值更小，还不如重新开始计算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func maxSubArray(nums []int) int {
    maxSum := math.MinInt // 最大连续和
    sum := 0
    for i := 0; i < len(nums); i++ {
       sum += nums[i]
       if sum > maxSum {
          maxSum = sum
       }
       if sum < 0 { // 如果sum小于0，舍弃前面得到的sum，将sum重置为0
          sum = 0
       }
    }
    return maxSum
}

买卖股票的最佳时机II

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

1
2
3
4
5
6
7
8


func main() {
    nums := []int{7, 1, 5, 3, 6, 4}
    r := maxProfit(nums)
    fmt.Println(r)
}
func maxProfit(prices []int) int {
    // ......
}

答案

我们可以计算每天可以获得的利润，如果利润大于 0，则将该利润加到 result 中。

1
2
3
4
5
6
7
8
9


func maxProfit(prices []int) int {
    res := 0
    for i := 1; i < len(prices); i++ { // 因为要第2天才能获得利润
       if prices[i] > prices[i-1] {
          res += prices[i] - prices[i-1]
       }
    }
    return res
}

跳跃游戏

55. 跳跃游戏

1
2
3
4
5
6
7
8


func main() {
    nums := []int{2, 0}
    r := canJump(nums)
    fmt.Println(r)
}
func canJump(nums []int) bool {
    // ......
}

答案

本题我们不需要关注每一步跳跃的长度，而是要关注当前的覆盖范围，然后使用贪心算法来获取我们当前可以获取到的最大覆盖范围。如果覆盖范围包括了数组的最后位置，那么就返回 true。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func canJump(nums []int) bool {
    if len(nums) == 1 {
       return true
    }
    cover := 0                    // 最大覆盖的范围
    for i := 0; i <= cover; i++ { // 这里要遍历覆盖范围内的元素
       cover = max(cover, i+nums[i]) // i+nums[i]表示当前位置往后能覆盖的范围，cover应该取二者的最大值
       if cover >= len(nums)-1 {
          return true
       }
    }
    return false
}

跳跃游戏II

45. 跳跃游戏 II

本题较为复杂，建议多加练习。

1
2
3
4
5
6
7
8


func main() {
    nums := []int{2, 3, 1, 1, 4}
    r := jump(nums)
    fmt.Println(r)
}
func jump(nums []int) int {
    // ......
}

答案

本题和跳跃游戏一样，我们不关心每一步具体是怎么跳跃的，我们只关心最少多少步可以调到末尾。

我们可以遍历当前的覆盖范围，在遍历当前覆盖范围时，记录下一步的最大覆盖范围（next）。

如果遍历当前的覆盖范围到尽头了，还没有到最后，就要增加步数，启动下一步的覆盖范围。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func jump(nums []int) int {
    if len(nums) == 1 {
       return 0
    }
    cur := 0                         // 当前覆盖的范围
    next := 0                        // 当前覆盖的范围内，下一步能走的最大范围
    res := 0                         // 需要的步数
    for i := 0; i < len(nums); i++ { // 从起始位置开始遍历
       next = max(i+nums[i], next) // i+nums[i]表示当前位置能跳到的位置，但是我们需要取当前范围内，下一步能跳的最远距离，所以需要和next取较大值
       if i == cur {               // 移动到了当前覆盖范围的最后，也没有到终点，就需要增加步数
          if cur < len(nums)-1 {
             res++
             cur = next              // 将下一步的覆盖范围赋给当前的覆盖范围
             if cur >= len(nums)-1 { // 当前的覆盖范围超过了最后的位置，终止循环
                break
             }
          } else {
             break
          }
       }
    }
    return res
}

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

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

1
2
3
4
5
6
7
8
9


func main() {
    nums := []int{-7, -1, 0, 2}
    k := 3
    r := largestSumAfterKNegations(nums, k)
    fmt.Println(r) // 10
}
func largestSumAfterKNegations(nums []int, k int) int {
	// ......
}

答案

先对 nums 数组进行自定义排序（按照绝对值从大到小排序）。

为什么要绝对值从大到小呢？因为我们的贪心算法要尽量让最大的负数变成正数，所以应该先遍历大的负数。

然后遍历数组，如果 nums[i]<0 且 k 大于 0，则将该负数变为正数，然后 k–。

如果遍历完了数组之后，还有剩余的 k（说明数组全部都变成非负数了）。

判断 k 是奇数还是偶数，如果是奇数，则将数组中最小的元素（最后一个元素）变成它的相反数。

如果 k 小于数组中负数的个数，最后的 if 语句也不会执行（因为 k==0）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func largestSumAfterKNegations(nums []int, k int) int {
    sort.Slice(nums, func(i, j int) bool {
       return math.Abs(float64(nums[i])) > math.Abs(float64(nums[j])) // i表示的是前一个下标，j表示的是后一个下标
    })
    for i := 0; i < len(nums); i++ {
       if nums[i] < 0 && k > 0 {
          nums[i] = -nums[i]
          k--
       }
    }
    if k%2 != 0 {
       nums[len(nums)-1] = -nums[len(nums)-1]
    }
    sum := 0
    for i := 0; i < len(nums); i++ {
       sum += nums[i]
    }
    return sum
}

加油站

134. 加油站

1
2
3
4
5
6
7
8
9


func main() {
    gas := []int{1, 2, 3, 4, 5}
    cost := []int{3, 4, 5, 1, 2}
    r := canCompleteCircuit(gas, cost)
    fmt.Println(r)
}
func canCompleteCircuit(gas []int, cost []int) int {
    // ......
}

答案

本题贪心算法的思路：遍历 gas 和 cost，计算二者的差值，得到当前剩余的油量 curSum。

如果累计的油量 curSum 小于0，那么我们就选择下一个位置作为起始位置，因为前面的剩余油量为负数，只会拖累我们，还是不如重新开始。

在遍历过程中，使用 totalSum 来累计每个位置剩余的油量（ gas[i] 和 cost[i] 的差值），这里把两个 for 循环合成了一个 for 循环。

如果遍历完成之后，发现 totalSum 小于 0，说明总油量小于总消耗，返回 -1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func canCompleteCircuit(gas []int, cost []int) int {
    curSum := 0
    totalSum := 0
    res := 0 // 表示可能的起始位置
    for i := 0; i < len(gas); i++ {
       curSum += gas[i] - cost[i]
       totalSum += gas[i] - cost[i]
       if curSum < 0 {
          curSum = 0
          res = i + 1
       }
    }
    if totalSum < 0 {
       return -1
    }
    return res
}

分发糖果

135. 分发糖果

1
2
3
4
5
6
7
8
9


func main() {
    ratings := []int{1, 2, 87, 87, 87, 2, 1}
    r := candy(ratings)
    fmt.Println(r) // 13
    // rArr: [1 2 3 1 3 2 1]
}
func candy(ratings []int) int {
    // ......
}

答案

本题我们需要保证：相邻两个孩子评分更高的孩子会获得更多的糖果。

这就需要比较 i 位置和 i-1 位置和 i+1 位置的评分，然后分配糖果。

为了防止分配的混乱，我们需要用两个 for 循环来进行比较，先比较左边的，再比较右边的。

我们使用 candyArr 数组保存每个位置分配的糖果数量。

第一个 for 循环，i 从 1 开始，如果 ratings[i]>ratings[i-1]，那么 candyArr[i]=candyArr[i-1]+1。第二个 for 循环，由于是比较 i 和 i+1，为了能复用之前计算得到的糖果数量，我们就必须从右边开始，然后往左边移动。

candyArr[i] 位置真正的糖果数量就应该取两次循环的得到的较大值。

最后计算 candyArr 数组的总和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func candy(ratings []int) int {
    sum := 0
    candyArr := make([]int, len(ratings))
    for i := 1; i < len(ratings); i++ {
       if ratings[i] > ratings[i-1] { // 比较左边
          candyArr[i] = candyArr[i-1] + 1
       }
    }
    for i := len(ratings) - 2; i >= 0; i-- {
       if ratings[i] > ratings[i+1] { // 比较右边
          candyArr[i] = max(candyArr[i+1]+1, candyArr[i]) // 去原来计算值和现在计算值的较大值
       }
    }
    for i := 0; i < len(candyArr); i++ {
       sum += candyArr[i]
    }
    fmt.Println(candyArr)
    sum += len(candyArr) // 由于每个位置至少分配一个糖果，所以需要加上n
    return sum
}

柠檬水找零

860. 柠檬水找零

1
2
3
4
5
6
7
8


func main() {
    bills := []int{5, 5, 5, 10, 20}
    r := lemonadeChange(bills)
    fmt.Println(r)
}
func lemonadeChange(bills []int) bool {
    // ......
}

答案

本题需要分析我们遇到的各种币值，并统计我们现在手中有的各种币值的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func lemonadeChange(bills []int) bool {
    five, ten := 0, 0 // 手中拥有各种币值的数量
    for i := 0; i < len(bills); i++ {
       if bills[i] == 5 {
          five++
       } else if bills[i] == 10 {
          if five > 0 {
             five--
             ten++
          } else {
             return false
          }
       } else if bills[i] == 20 {
          if ten > 0 && five > 0 { // 优先使用10+5的组合
             ten--
             five--
          } else if five >= 3 { // 没有前面的，就用3个5
             five -= 3
          } else {
             return false
          }
       }
    }
    return true
}

根据身高重建队列

406. 根据身高重建队列

1
2
3
4
5
6
7
8


func main() {
    people := [][]int{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}}
    r := reconstructQueue(people)
    fmt.Println(r) // [[5 0] [7 0] [5 2] [6 1] [4 4] [7 1]]
}
func reconstructQueue(people [][]int) [][]int {
    // ......
}

答案

每个一维数组有两个维度，一个是身高 h，一个是 k，表示它前面有多少个大于等于它的元素。

我们可以先对二维数组进行排序（排序规则为先按照 h 降序，如果 h 相同，再按照 k 升序）

然后再遍历二维数组，将一维数组根据 k 的值，插入到它应该在的位置。

由于 i 位置元素前面的元素 h 都比它大，所以 k 的位置就是二维数组的下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func reconstructQueue(people [][]int) [][]int {
    sort.Slice(people, func(i, j int) bool { // 先按照h降序，再按照k升序
       if people[i][0] != people[j][0] {
          return people[i][0] > people[j][0]
       } else {
          return people[i][1] < people[j][1]
       }
    })
    for i := 1; i < len(people); i++ {
       // 按照k值插入元素
       insertItem := people[i] // 要插入的元素
       if insertItem[1] != i { // insertItem[1]表示元素应该插入的位置，i表示元素现在的位置
          j := i
          for ; j > insertItem[1]; j-- { // 将前面元素后移
             people[j] = people[j-1]
          }
          people[j] = insertItem
       }
    }
    return people
}

用最少数量的箭引爆气球

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

1
2
3
4
5
6
7
8


func main() {
    points := [][]int{{10, 16}, {2, 8}, {1, 6}, {7, 12}}
    r := findMinArrowShots(points)
    fmt.Println(r) // 2
}
func findMinArrowShots(points [][]int) int {
    // ......
}

答案

本题需要明确什么时候气球与气球之间存在重叠。

我们先对 points 数组按照左边界进行排序（方便我们的遍历过程）

当一个气球的左边界小于等于前一个气球的右边界时，表示两个气球存在重叠。

那我们如何确定需要使用的弓箭数呢？

如果气球不重叠，则弓箭数量加 1。

如果当前气球和前一个气球重叠了，那我们就要将当前气球的右边界更新为：当前气球的右边界和前一个气球的右边界中的较小值。

因为这个范围可以被同一个弓箭射中，而且我们在前面已经统计了该弓箭，我们只需要更新右边界的值即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func findMinArrowShots(points [][]int) int {
    sort.Slice(points, func(i, j int) bool {
       return points[i][0] < points[j][0]
    })
    arrowCount := 1 // 弓箭数至少为1，因为我们判断的是从第二个开始的气球是否和前面的气球重叠，不重叠我们才增加气球数量
    for i := 1; i < len(points); i++ {
       if points[i][0] > points[i-1][1] { // 当前气球的左边界大于前一个气球的右边界，表示不存在重叠
          arrowCount++
       } else { // 存在重叠，计算重叠气球中最左边的右边界
          points[i][1] = min(points[i-1][1], points[i][1])
       }
    }
    return arrowCount
}

无重叠区间

435. 无重叠区间

1
2
3
4
5
6
7
8


func main() {
    intervals := [][]int{{1, 2}, {2, 3}, {3, 4}, {1, 3}}
    r := eraseOverlapIntervals(intervals)
    fmt.Println(r) // 1
}
func eraseOverlapIntervals(intervals [][]int) int {
    // ......
}

答案

本题和用最少数量的箭引爆气球一样，要对区间重叠进行判断。

先按照 intervals 的左边界排序。

如果 intervals[i] 的左边界大于等于 intervals[i-1] 的右边界，说明二者是不重叠的，否则，二者是重叠的。

如果发生了重叠，我们要记录重叠的右边界（将当前元素的右边界更新为重叠部分的右边界）。

我们统计了重叠区间的数量，只要删除这些重叠区间，就可以让整个数组没有重叠区间了，所以重叠区间的数量就是要删除的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
       return intervals[i][0] < intervals[j][0]
    })
    lapCount := 0
    for i := 1; i < len(intervals); i++ {
       if intervals[i][0] < intervals[i-1][1] { // 重叠
          lapCount++
          intervals[i][1] = min(intervals[i-1][1], intervals[i][1]) // 更新重叠部分的右边界
       }
    }
    return lapCount
}

划分字母区间

763. 划分字母区间

1
2
3
4
5
6
7
8


func main() {
    s := "ababcbacadefegdehijhklij"
    r := partitionLabels(s)
    fmt.Println(r) // [9 7 8]
}
func partitionLabels(s string) []int {
    // ......
}

答案

本题需要先遍历字符串 s，记录 s 中每个字母出现的最远位置（index 最大）

然后再次变量 s，获取当前区间（第 0 个元素到出现过的元素的最远位置）字母的最远位置的最大值 right。

使用 left 记录当前区间的最左侧。

如果 i==right，说明该区间已经把所有的出现过的字母都包含了，将该区间长度添加到 res 中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func partitionLabels(s string) []int {
    res := make([]int, 0)
    charMaxIndex := make(map[byte]int) // 每个字母出现的最大下标
    left := 0
    right := 0
    for i := 0; i < len(s); i++ {
       charMaxIndex[s[i]] = i
    }
    fmt.Println(charMaxIndex)
    for i := 0; i < len(s); i++ {
       right = max(right, charMaxIndex[s[i]]) // 获取当前区间元素右边的位置
       if i == right {                        // 把当前区间遍历完了
          res = append(res, right-left+1)
          left = right + 1 // 更新left为right+1，用户获取下一个区间的长度
       }
    }
    return res
}

合并区间

56. 合并区间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func main() {
	intervals := [][]int{{1, 3}, {8, 10}, {2, 6}, {15, 18}} // [[1 6] [8 10] [15 18]]
	//intervals := [][]int{{2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10}} // [[1 10]]
	//intervals := [][]int{{1, 4}, {5, 6}} // [[1 4] [5 6]]
    r := merge(intervals)
    fmt.Println(r)
}
func merge(intervals [][]int) [][]int {
    // ......
}

答案

本题我们也需要判断区间是否重叠，我们需要将重叠的区间合并，先按照区间的左侧值进行排序，然后合并重叠区间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func merge(intervals [][]int) [][]int {
	if len(intervals) == 1 {
		return intervals
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	fmt.Println(intervals)
	res := make([][]int, 1)
	res[0] = intervals[0]
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] <= res[len(res)-1][1] { // 本元素的左侧小于等于前一个元素（合并后）的右侧，说明重叠了
			// 合并区间（这里合并得很有技巧）
			res[len(res)-1][1] = max(res[len(res)-1][1], intervals[i][1]) // 更新res中最后一个元素的右坐标
		} else {
			res = append(res, intervals[i])
		}
	}
	return res
}

单调递增的数字

738. 单调递增的数字

1
2
3
4
5
6
7
8


func main() {
    n := 332
    r := monotoneIncreasingDigits(n)
    fmt.Println(r)
}
func monotoneIncreasingDigits(n int) int {
    // ......
}

答案

先将 n 转换为字符串 str，然后从后往前遍历 str。

如果 str[i]>str[i+1]，就将 i 位置的值减去 1，并用 flag 标识 i 位置，flag 位置后面的位置都应该设置为 9。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func monotoneIncreasingDigits(n int) int {
    str := strconv.Itoa(n)
    strByte := []byte(str)
    flag := len(strByte)
    for i := len(strByte) - 2; i >= 0; i-- {
       if strByte[i] > strByte[i+1] {
          strByte[i] = strByte[i] - 1
          flag = i // flag后面的位置都应该设置为9
       }
    }
    for i := flag + 1; i < len(strByte); i++ {
       strByte[i] = '9'
    }
    num, _ := strconv.Atoi(string(strByte))
    return num
}

监控二叉树

968. 监控二叉树

本题过于复杂，可以先战略性跳过。

参考：代码随想录——0968.监控二叉树

收录于合集・代码随想录 7

代码随想录：回溯算法代码随想录：动态规划