用 Python 编写程序，查找经过所有站点所需的最少公交车数量

pythonserver side programmingprogramming更新于 2026/1/9 3:56:17

假设我们有一个名为 nums 的数字列表，该列表在一行上显示公交车站，其中 nums[i] 显示公交车必须到达车站 i 的时间。既然公交车只能向前行驶，我们必须找到经过所有站点所需的最少公交车数量。

因此，如果输入为 nums = [1, 2, 7, 9, 3, 4]，则输出将为 2，因为一辆公交车可以停靠 [1, 2, 3, 4] 站，另一辆公交车可以停靠 [7, 9] 站。

为了解决这个问题，我们将遵循以下步骤−

ans := 0
seen := 一个长度与 nums 相同且最初填充为 false 的列表
对于 nums 中的每个索引 i 和对应的 n，执行
- 如果 seen[i] 为 false，则
  - seen[i] := True
  - ans := ans + 1
  - prev := n
  - 对于 j，在 i+1 到 nums 大小的范围内，执行
    - 如果 nums[j] > prev 且 seen[j] 为 false，则
      - seen[j] := True
      - prev := nums[j]
返回 ans

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, nums):
   ans = 0
   seen = [False] * len(nums)
   for i, n in enumerate(nums):
      if not seen[i]:
         seen[i] = True
         ans += 1
         prev = n
   for j in range(i+1, len(nums)):
      if nums[j] > prev and not seen[j]: seen[j] = True
         prev = nums[j]
   return ans
ob = Solution()
nums = [1, 2, 7, 9, 3, 4]
print(ob.solve(nums))