分配问题

📌 核心概念

分配问题通常需要排序后进行贪心匹配，核心思想是让需求最小的优先匹配，或让资源最优分配。

贪心策略：排序后双指针或直接遍历匹配。

💻 算法实现

🎯 经典应用

💡 解题技巧

📊 复杂度分析

问题	时间复杂度	空间复杂度	关键点
分发饼干	O(n log n)	O(1)	排序+双指针
分发糖果	O(n)	O(n)	两次遍历
分配自行车	O(mn log mn)	O(mn)	排序+集合
任务调度器	O(n)	O(1)	计数+公式
重构字符串	O(n log 26)	O(1)	堆+贪心

Go 代码

import "sort"
 
// 分发饼干
func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
 
    child := 0
    for cookie := 0; cookie < len(s) && child < len(g); cookie++ {
        if s[cookie] >= g[child] {
            child++
        }
    }
 
    return child
}
 
// 分发糖果
func candy(ratings []int) int {
    n := len(ratings)
    if n == 0 {
        return 0
    }
 
    candies := make([]int, n)
    for i := range candies {
        candies[i] = 1
    }
 
    // 从左到右
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }
 
    // 从右到左
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            candies[i] = max(candies[i], candies[i+1]+1)
        }
    }
 
    sum := 0
    for _, c := range candies {
        sum += c
    }
 
    return sum
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

🎯 经典题目

题目	LeetCode	难度	关键点
分发饼干	455	简单	排序+双指针
分发糖果	135	困难	两次遍历
分配自行车	1057	中等	多维排序
任务调度器	621	中等	计数+公式
重构字符串	767	中等	堆+贪心
书店老板	1052	中等	滑动窗口
根据身高重建队列	406	中等	排序+插入

---

返回：贪心算法