分发饼干（力扣455）

文章目录

• 题目
• 贪心算法
• • 思想概述
  • 关键要素
  • 解题步骤
  • 优缺点
  • • 优点
    • 缺点
  • 应用领域
• 题解
• • 一、思路
  • 二、解题方法
  • 三、Code
• 总结

题目

Problem: 455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 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。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

贪心算法

当我们谈论贪心算法（Greedy Algorithm）时，我们实际上在讨论一种基于贪心策略的算法思想。它通常用于解决最优化问题，其中问题的解决方案可以通过一系列局部最优选择来逐步构建全局最优解。

思想概述

贪心算法的核心思想是每一步都选择当前状态下的最佳解决方案，而不考虑之后步骤可能带来的影响。这种“贪心”策略意味着在每个阶段做出局部最优的选择，希望最终达到全局最优。贪心算法并不总是能够找到问题的最优解，但在某些情况下却能得到接近最优解的结果。

关键要素

1. 最优子结构性质： 问题的最优解可以通过子问题的最优解来推导。这意味着问题的整体最优解可以通过局部最优解来构建。

2. 贪心选择性质： 贪心算法每一步都选择局部最优解，而不考虑之后的结果。这种选择性质确保了局部最优解的累积能够构成全局最优解。

解题步骤

• 确定问题的贪心策略： 首先要明确在当前状态下应该如何做出局部最优选择，即确定贪心策略。

• 将问题划分为子问题： 确定好贪心策略后，将问题划分为一系列子问题，每个子问题都可以独立求解。

• 逐步构建解决方案： 根据贪心策略，逐步构建问题的解决方案，每一步都做出局部最优选择。

• 检查是否满足最优性： 在构建解决方案的过程中，需要时刻检查所做的局部最优选择是否满足最优性质。有时候需要证明该贪心策略确实能够得到全局最优解。

优缺点

优点

• 算法简单、容易实现。

• 执行速度快，通常时间复杂度较低。

• 适用于一些特定类型的问题，能够找到近似最优解。

缺点

• 不能保证得到全局最优解，可能会陷入局部最优解。
• 需要证明贪心策略满足最优性质，有时比较困难。
• 不适用于所有类型的问题，有些问题并不适合贪心算法。

应用领域

贪心算法在许多领域都有应用，特别是那些满足最优子结构性质的问题，如：最短路径问题，最小生成树问题，区间覆盖问题，部分背包问题，活动选择问题，哈夫曼编码等。在这些问题中，贪心算法可以提供高效的解决方案，使其成为解决实际问题的有力工具。

题解

一、思路

通过局部最优推到全局最优，这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。使用贪心策略，先将饼干数组和小孩数组排序

然后从前向后遍历小孩数组，用小饼干优先满足胃口小的，并统计满足小孩数量。
或者从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。如下图为第二种方法：

二、解题方法

排序两个数组，count计数喂饱了几个孩子，从前往后先遍历饼干尺寸s，start下标从胃口g开始遍历，当饼干满足胃口时，start下标才向后移动一位，否则继续遍历饼干尺寸直到找到刚好满足胃口的饼干尺寸。

for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }

还有一种情况就是让start指向最大的饼干尺寸，从后往前先遍历胃口g，如果找到满足最大胃口的最大饼干尺寸s的话，就找下一块更小的饼干

for (int index = g.length - 1; index >= 0; index--) {
            if(start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }

注意事项：这里遍历的顺序不能改变，如果是从前往后遍历的话，要先遍历饼干的尺寸，再遍历胃口；而如果是从后往前遍历的话，要先遍历胃口，再遍历饼干的尺寸。

如果是从后往前先对尺寸遍历再遍历胃口的话，当胃口比所有饼干的尺寸都大的话，那么直到所有尺寸都遍历完的时候，if条件内也不会走逻辑。外面的 for 是里的下标 i 是固定移动的，而 if 里面的下标 index 是符合条件才移动的。就是出现如下情况：

if 里的 index 指向 胃口 10， for 里的 i 指向饼干 9，因为 饼干 9 满足不了 胃口 10，所以 i 持续向前移动，而 index 走不到s[index] >= g[i] 的逻辑，所以 index 不会移动，那么当 i 持续向前移动，最后所有的饼干都匹配不上。

三、Code

小饼干先喂饱小胃口

class Solution {
    // 思路1：优先考虑饼干，小饼干先喂饱小胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = 0;

        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
        return count;
    }
}

大饼干先喂饱大胃口

class Solution {
    // 思路2：优先考虑胃口，先喂饱大胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        // 遍历胃口
        for (int index = g.length - 1; index >= 0; index--) {
            if(start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }
        return count;
    }
}

总结

以上就是针对这道题的刷题笔记，用到了贪心算法解决分发饼干问题，通过找到充分利用饼干尺寸喂饱一个小孩局部最优解从而推出全局最优解。希望这篇题解能够帮助到你解决这个问题。如果有任何疑问或者建议，欢迎留言讨论！