BM95　分糖果问题¶

较难通过率 23.72%python3核心代码模式样例通过牛客 AC贪心

讲解章节：贪心

一句话

左右各扫一遍分别满足两个方向的约束，逐位取较大者。

解题思路¶

这题考什么¶

把一个看似互相牵扯的约束系统拆成两条彼此独立的链式规则：

左规则：arr[i] > arr[i-1]  =>  candy[i] > candy[i-1]
右规则：arr[i] > arr[i+1]  =>  candy[i] > candy[i+1]

一次遍历同时兼顾两边很容易顾此失彼——刚为了右邻居加了糖，又破坏了与左邻居的关系。拆开之后每条规则都只依赖单一方向，各扫一遍就能取到各自的最小可行解。

第一遍从左往右只管左规则：得分递增时 left[i] = left[i-1] + 1，否则重置为 1。第二遍从右往左只管右规则：得分递减时 right[i] = right[i+1] + 1，否则重置为 1。最终 candy[i] = max(left[i], right[i])，求和即答案。

取 max 而不是相加：两条规则各自给出了 candy[i] 的一个下界，同时满足两者的最小取值就是两个下界里较大的那个。相加会白白多发糖。另外 left 与 right 的下限都是 1，max 自动保证了「每人至少一颗」这条要求。得分相等时两边都重置为 1，正好对应题面「若相同则无此限制」。这是贪心里典型的「按维度拆解后各自取局部最小」，见贪心。

手推 [1,2,2,5,3,1]：

arr    1  2  2  5  3  1
left   1  2  1  2  1  1     只看左邻居，递增就在前一个基础上 +1
right  1  1  1  3  2  1     只看右邻居，递减就在后一个基础上 +1
max    1  2  1  3  2  1  -> 合计 10

数据规模与复杂度¶

1 <= n <= 1e5，得分 1 <= a_i <= 1000，时限「其他语言 4 秒」，题面要求时间 O(n)、空间 O(n)。两遍线性扫描，时间 O(n)。本实现只开一个数组：第一遍把左规则的结果写进 res，第二遍从右往左用一个标量 run 维护右规则的连续长度，边算边与 res[i] 取较大者，顺手把总和累加出来，空间仍是 O(n) 但常数减半。与之相对，「反复扫描直到没有位置需要调整」的朴素修补法在单调递增序列上要扫 n 遍，是 O(n^2) = 1e10。

坑在哪¶

第二遍必须与第一遍的结果取 max，不能直接覆盖。直接写 res[i] = run 会毁掉左规则已经保证的下界， [1,2,3,2,1] 这类先升后降的形状上立刻出错。
两条规则的重置值都是 1，不是 0。题面要求每个孩子起码分到一颗糖。
第二遍的循环从 n-2 起、步长 -1 走到 0：n-1 是右规则的边界（没有右邻居），它的糖数在第一遍里已经定下，所以总和的初值直接取 res[n-1]，循环体内不再重复累加这一位。
得分相等时两边都不加糖。误把相等也算作「较多」， [1,1,1] 会得到 6 而不是正确的 3。
空数组要先挡住：n = 0 时 res[n-1] 会取到 res[-1]，在 Python 里不报错而是取到末尾元素，属于静默的错误答案。题面虽然保证 n >= 1，但这一层短路的代价只有一行。

参考实现¶

solutions/nowcoder/BM95/sol.py
from typing import List, Optional


class Solution:
    def candy(self, arr: List[int]) -> int:
        n = len(arr)
        # 空数组要先挡住：否则下面 res[n-1] 变成 res[-1]，在 Python 里静默取到末元素
        if n == 0:
            return 0
        res = [1] * n                 # 每人至少一颗，这也是两条规则的公共下界
        # 第一遍从左往右：只保证「比左邻居分高就比左邻居糖多」，得分不增时留在 1
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                res[i] = res[i - 1] + 1
        # 第二遍从右往左补右规则。run 是标量版的 right[i]，省掉第二个数组
        run = 1                       # 当前位置按右规则应得的糖数
        total = res[n - 1]            # 末位没有右邻居，第一遍的结果即最终值，先计入
        # 从 n-2 起倒着走：末位已经结算过，所以起点比末下标少一格
        for i in range(n - 2, -1, -1):
            run = run + 1 if arr[i] > arr[i + 1] else 1
            # 与左规则的下界取较大者：两条规则各给一个下界，同时满足两者取 max 即最小
            if run > res[i]:
                res[i] = run
            total += res[i]
        return total

BM95 分糖果问题¶