想法

贪心算法与思维详解

贪心算法是一种逐步构建解的策略，每一步都做出一个当前看似最优的选择。其核心思想是局部最优解能导致全局最优解。

---

1. 基本贪心策略

贪心策略的核心是：

• 确定“贪心选择”的原则（局部最优）。
• 判断贪心选择能否推导出全局最优解（贪心的可行性）。
• 多通过数学证明或反例验证贪心选择的正确性。

模板

以最小字典序为例：

func smallestSubsequence(s string) string {
    stack := []byte{}
    seen := make(map[byte]bool)
    count := make(map[byte]int)
    
    for _, c := range s {
        count[byte(c)]++
    }

    for _, c := range s {
        count[byte(c)]--
        if seen[byte(c)] {
            continue
        }

        for len(stack) > 0 && stack[len(stack)-1] > byte(c) && count[stack[len(stack)-1]] > 0 {
            seen[stack[len(stack)-1]] = false
            stack = stack[:len(stack)-1]
        }

        stack = append(stack, byte(c))
        seen[byte(c)] = true
    }
    return string(stack)
}

---

2. 贪心与反悔

反悔策略

反悔是通过在贪心过程中“撤销某些选择”，从而使得最终结果更优的技巧。

问题：最大子序列和

给定一个数组，选出固定长度的子序列，使得和最大。

思路：

• 使用优先队列保存最大值，同时允许在必要时弹出较小值。

func maxSubsequence(nums []int, k int) []int {
    n := len(nums)
    stack := make([]int, 0, k)
    
    for i := 0; i < n; i++ {
        for len(stack) > 0 && len(stack)+n-i > k && stack[len(stack)-1] < nums[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) < k {
            stack = append(stack, nums[i])
        }
    }
    return stack
}

---

3. 区间问题

贪心算法在区间问题中非常高效，尤其是在覆盖、合并、最小化或最大化选择的场景。

区间覆盖

问题：活动选择

给定 ( n ) 个活动，每个活动有一个开始时间和结束时间，选择尽可能多的互不重叠的活动。

贪心思路：

1. 按结束时间升序排序。
2. 每次选择结束时间最早的活动，并更新可选区间。

func activitySelection(start, end []int) int {
    n := len(start)
    intervals := make([][2]int, n)
    for i := 0; i < n; i++ {
        intervals[i] = [2]int{end[i], start[i]}
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    count, lastEnd := 0, -1
    for _, interval := range intervals {
        if interval[1] > lastEnd {
            count++
            lastEnd = interval[0]
        }
    }
    return count
}

---

4. 贪心与字典序

贪心策略在构造最小或最大字典序时常用。

最小字典序问题

问题：移掉 K 位数字

与单调栈方法类似，贪心地保持当前数列的递增。

---

5. 贪心与数学

贪心算法在数学问题中多用于解决分数、数列、和等问题。

问题：最小硬币数量

给定面值硬币，求最少硬币组合达到某金额。

func coinChange(coins []int, amount int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(coins)))
    count := 0
    for _, coin := range coins {
        count += amount / coin
        amount %= coin
    }
    if amount > 0 {
        return -1 // 无法凑齐
    }
    return count
}

---

6. 贪心与思维

贪心策略也常在脑筋急转弯和特殊构造问题中应用。

问题：分配饼干

给定孩子的需求值和饼干大小，问最多能满足几个孩子。

贪心思路：

1. 优先满足需求最小的孩子。
2. 尽可能使用最小的饼干。

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)

    i, j, count := 0, 0, 0
    for i < len(g) && j < len(s) {
        if s[j] >= g[i] {
            count++
            i++
        }
        j++
    }
    return count
}

---

7. 贪心与构造

贪心常用于“构造”问题。

问题：构造回文数

给定一个字符串，构造一个最短的回文字符串。

思路：

• 从两端向内扫描，贪心选择需要填补的字符。

---

总结

• 适用场景：贪心问题通常有明确的“最优子结构”。
• 验证方式：
  • 构造反例测试。
  • 结合数学推导。
• 经典问题：活动选择、区间覆盖、最小字典序、数列构造等。