LeetCode 筆記 - 1696. Jump Game VI

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        
        if (size := len(nums)) == 1:
            return nums[0]
        
        if k == 1:
            return sum(nums)
        
        score = nums[0]
        priority_queue = []
        
        # since heapq is a min-heap,
        # we use negative of the numbers to mimic a max-heap
        heapq.heappush(priority_queue, (-nums[0], 0))
        
        for i in range(1, size):

            # pop the old index
            while priority_queue[0][1] < i - k:
                heapq.heappop(priority_queue)
                
            score = nums[i] - priority_queue[0][0]
            heapq.heappush(priority_queue, (-score, i))
            
        return score