BinarySearch 0646 Costly Flight of Stairs

Problem statement

https://binarysearch.com/problems/Costly-Flight-of-Stairs/

Solution

Equal to Leetcode 1696. Jump Game VI, but here we need to do minimums.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        deq, n = deque([0]), len(nums)

        for i in range(1, n):
            while deq and deq[0] < i - k: deq.popleft()
            nums[i] += nums[deq[0]]   
            while deq and nums[i] <= nums[deq[-1]]: deq.pop()
            deq.append(i)
            
        return nums[-1]