BinarySearch 0366 Bunnyhopping

Problem statement

https://binarysearch.com/problems/Bunnyhopping/

Solution

Equal to Leetcode 1696. Jump Game VI, but change min with max here.

Complexity

Time and space is O(n).

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]