Leetcode # 2361. Minimum Costs Using the Train Line

https://leetcode.com/problems/minimum-costs-using-the-train-line

Solution

• n := len(regular) == len(express)
• prev[0/1] := 前一站為止留在 regular/express 車廂上的最小 cost

Time Complexity: O(n)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minimumCosts(self, regular: List[int], express: List[int], expressCost: int) -> List[int]:
    prev = [0, expressCost]
    costs = [0 for _ in range(len(regular))]
    for i in range(len(regular)):
      next_r = regular[i] + min(prev[1], prev[0])
      next_e = express[i] + min(prev[1], prev[0] + expressCost)
      prev = [next_r, next_e]
      costs[i] = next_r if next_r < next_e else next_e
    return costs

Last Updated on 2023/08/16 by A1go