实现num_charging_stops函数遇问题：输出不符+求最优解法

函数定义 #

from typing import List

def num_charging_stops(legs: List[int], capacity: int) -> int:

功能说明 #

• 行程中的每一段leg代表行驶该段所需的能量
• 行驶完每段后可选择充电（电量恢复至capacity）或不充电
• 初始电池为满电状态，必须保证行驶过程中电量始终≥0
• 若无法完成全部行程，返回-1

示例用例 #

尝试的代码 #

from typing import List

def num_charging_stops(legs: List[int], capacity: int) -> int:
    current_energy = capacity
    charging_stops = 0

    for leg in legs:
        current_energy -= leg

        if current_energy < 0:
            current_energy = capacity
            charging_stops += 1

    if current_energy < 0:
        return -1

    return charging_stops

现有问题 #

1. 代码输出不符合预期，当前运行结果为：0、1、1、1、1（与第5个用例的预期输出2不符）
2. 是否存在更优的解决方案？

问题分析与修正 #

现有代码的核心缺陷 #

现有代码逻辑完全颠倒了判断顺序：它先扣除当前路段的能耗，发现电量不足后再充电，但这已经违反了“行驶中电量不能低于0”的要求——如果当前电量不足以支撑这段路程，根本无法启动行驶。此外，代码没有提前检查是否存在单段路程能耗超过电池容量的情况，这种情况下直接就无法完成行程。

正确的贪心实现（最优解） #

要得到最少充电次数，最优策略是尽可能晚充电：只有当当前电量不足以支撑下一段路程时，才进行充电。这是典型的贪心算法应用，能保证最少的停靠次数。

修正后的代码：

from typing import List

def num_charging_stops(legs: List[int], capacity: int) -> int:
    # 先排查无法完成的情况：单段路程超过电池容量
    for leg in legs:
        if leg > capacity:
            return -1
    
    current_energy = capacity
    charging_stops = 0
    
    for leg in legs:
        # 电量不够支撑当前路段，必须先充电
        if current_energy < leg:
            charging_stops += 1
            current_energy = capacity
        
        # 行驶当前路段，扣除能耗
        current_energy -= leg
    
    return charging_stops

代码验证 #

用所有示例用例测试：

• [25], 30：初始30足够行驶25，无需充电，返回0
• [25,25],30：行驶25后剩5，不够下一段25，充电（次数+1）后满电，行驶25剩5，返回1
• [50],30：单段超过容量，返回-1
• [15,15,30],30：行驶前两段后剩0，不够第三段30，充电（次数+1）后满电，行驶30剩0，返回1
• [15,30,15],30：行驶15后剩15，不够30，充电（次数+1）；行驶30后剩0，不够15，再充电（次数+2），返回2

所有结果均符合预期。

关于最优解 #

上述贪心算法的时间复杂度为O(n)，空间复杂度为O(1)，是理论上的最优方案。因为它只需要遍历一次路段列表，没有额外的空间开销，无法再优化时间或空间复杂度。

内容的提问来源于stack exchange，提问作者user1234