Pythonのすべての停留所を通過するには、バスの最小数を見つけるプログラムが必要です

numsという番号のリストがあり、バス停が路線上にあることを示しているとします。ここで、nums[i]はバスが駅iに到着する必要がある時間を示しています。バスは前進することしかできないので、すべての停留所を通過するために必要なバスの最小数を見つける必要があります。

したがって、入力がnums =[1、2、7、9、3、4]の場合、1つのバスが[1、2、3、4]を停止し、別のバスが[1、2、3、4]を停止できるため、出力は2になります。 7、9]。

これを解決するために、次の手順に従います-

• ans：=0

• 見られる：=長さがnumsと同じで、最初はfalseで埋められたリスト

• 各インデックスiおよび対応するnの数について、実行します

  • 見た[i]が偽の場合、

    • 見た[i]：=真

    • ans：=ans + 1

    • 前：=n

    • i + 1からnumsのサイズまでの範囲のjについては、次のようにします

      • nums [j]>prevおよびseen[j]がfalseの場合、

        • 見た[j]：=真

        • 前：=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))

入力

[1, 2, 7, 9, 3, 4]

出力

2