0135. Candy =========== 题目信息 -------- :题号: 0135. 分发糖果 :难度: Hard :主题: 贪心、双向扫描、局部约束、状态压缩 :原题: `LeetCode 0135 `_ :重点: 将每个孩子来自左右邻居的要求拆成两个最小下界,逐点取最大值,再滚动压缩一个方向 题目重述 -------- 一列孩子按顺序给出评分 ``ratings``。每个孩子至少得到一颗糖;若某个孩子评分严格高于相邻孩子,他得到的 糖也必须严格更多。相邻评分相等时没有大小关系。返回满足所有相邻约束的最少糖果总数。 自建示例 -------- * ``ratings = [1, 3, 2, 2, 1]``:最小分配为 ``[1, 2, 1, 2, 1]``,总数 ``7``; * ``ratings = [1, 2, 3, 2, 1]``:山峰需要分配 ``[1, 2, 3, 2, 1]``,总数 ``9``; * ``ratings = [5, 5, 5]``:相等评分不产生额外约束,每人一颗,总数 ``3``; * ``ratings = [4]``:只有一个孩子,返回 ``1``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int repeatedlyRepairConstraints(const std::vector& ratings) { const int childCount = static_cast(ratings.size()); std::vector candies(childCount, 1); bool changed = true; while (changed) { changed = false; for (int index = 0; index + 1 < childCount; ++index) { if (ratings[index] > ratings[index + 1] && candies[index] <= candies[index + 1]) { candies[index] = candies[index + 1] + 1; changed = true; } if (ratings[index] < ratings[index + 1] && candies[index] >= candies[index + 1]) { candies[index + 1] = candies[index] + 1; changed = true; } } } return std::accumulate(candies.begin(), candies.end(), 0); } int twoDirectionalArrays(const std::vector& ratings) { const int childCount = static_cast(ratings.size()); std::vector fromLeft(childCount, 1); std::vector fromRight(childCount, 1); for (int index = 1; index < childCount; ++index) { if (ratings[index] > ratings[index - 1]) { fromLeft[index] = fromLeft[index - 1] + 1; } } for (int index = childCount - 2; index >= 0; --index) { if (ratings[index] > ratings[index + 1]) { fromRight[index] = fromRight[index + 1] + 1; } } int total = 0; for (int index = 0; index < childCount; ++index) { total += std::max(fromLeft[index], fromRight[index]); } return total; } int oneArrayAndRollingRight(const std::vector& ratings) { const int childCount = static_cast(ratings.size()); std::vector fromLeft(childCount, 1); for (int index = 1; index < childCount; ++index) { if (ratings[index] > ratings[index - 1]) { fromLeft[index] = fromLeft[index - 1] + 1; } } int rightRequirement = 1; int total = fromLeft[childCount - 1]; for (int index = childCount - 2; index >= 0; --index) { if (ratings[index] > ratings[index + 1]) { ++rightRequirement; } else { rightRequirement = 1; } total += std::max(fromLeft[index], rightRequirement); } return total; } public: int candy(std::vector& ratings) { return oneArrayAndRollingRight(ratings); } }; 题解 ---- 原始做法:从全一分配反复修补 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 先给每人一颗,再扫描每对相邻孩子:高评分者若没有更多糖,就把他的糖数提高到低评分者加一。持续扫描到 没有变化,最终一定满足约束。``repeatedlyRepairConstraints`` 只会增加糖数,并且每次只增加到当前约束 要求的最低值,因此它能作为直觉正确的基线。 瓶颈是约束会沿长坡传播。对严格递减评分,左到右扫描先修补靠左位置后,右侧变化又会迫使前面在下一轮继续 增加;同一位置可能被访问和修改多次,最坏需要 ``O(n^2)`` 工作。问题不是局部规则难检查,而是一个扫描 方向无法让两侧依赖都处于已知状态。 把一条双向规则拆成两个单向下界 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 每个孩子可能同时受到左右邻居约束。先只考虑左邻居,定义 ``fromLeft[i]`` 为满足以下条件的最少糖数: * 每人至少一颗; * 若 ``ratings[i] > ratings[i-1]``,则当前位置比左侧多一颗。 从左向右时依赖已经算好,所以严格上升就取前一值加一,否则回到一。类似地,``fromRight[i]`` 从右向左 计算,只负责评分高于右邻居的约束。相等评分在该方向没有“更多”要求,必须重置为一,不能让前一段坡度 跨过平台传播。 为何逐点取最大值而不是相加 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 任意合法分配都必须同时不小于左右两个下界,所以位置 ``i`` 至少需要 ``max(fromLeft[i], fromRight[i])``。反过来,取这个最大值后:若评分高于左邻居,``fromLeft`` 保证当前值 大于左侧最终值所需的左向链长度;若评分高于右邻居,``fromRight`` 对称保证。两个方向的全部约束因此同时 成立。 这个逐点下界本身可行,所以不只是必要下界,也是全局最小分配。相加会重复计算同一颗糖:在山峰 ``[1, 2, 3, 2, 1]`` 中,峰值左右要求都是三颗,满足两侧只需三颗,不是六颗。 具体走读平台与山峰 ~~~~~~~~~~~~~~~~~~ 对 ``ratings = [1, 3, 2, 2, 1]``: .. list-table:: :header-rows: 1 * - 评分 - 左向下界 - 右向下界 - 最终取值 * - ``1`` - ``1`` - ``1`` - ``1`` * - ``3`` - ``2`` - ``2`` - ``2`` * - ``2`` - ``1`` - ``1`` - ``1`` * - ``2`` - ``1`` - ``2`` - ``2`` * - ``1`` - ``1`` - ``1`` - ``1`` 中间两个评分相等的 ``2`` 之间没有糖数关系,所以第一段下降在平台处结束;右侧那个 ``2`` 只因高于末尾 ``1`` 才需要两颗。 右向数组怎样压缩为一个变量 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 合并答案时本来就要从右向左。计算 ``fromRight[i]`` 只依赖刚算出的 ``fromRight[i+1]``,而更右侧状态在 加入总和后不会再次使用,所以整张右向数组可以压缩为 ``rightRequirement``。严格下降时加一,否则重置为 一,再与已保存的 ``fromLeft[i]`` 取最大值。 最后一个孩子没有右邻居,右向下界为一;代码先把他的左向值加入 ``total``,再从倒数第二个位置开始滚动。 这避免访问越界,也覆盖单元素数组:循环不执行,结果就是一。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用左向数组加滚动右状态,时间 ``O(n)``、空间 ``O(n)``。双数组方案同为线性时间,但使用两份 ``O(n)`` 状态,保留它是为了直接展示两个独立下界;滚动版本进一步删除右数组。反复修补只需一个糖果数组, 却可能花 ``O(n^2)`` 时间,因此仅作为原始搜索方式。返回结果按题目约束可用 ``int`` 表示。