1696. 跳跃游戏 VI

1696. 跳跃游戏 VI

• 难度: medium
• 原始链接: https://leetcode.cn/problems/jump-game-vi
• 标签: 单调栈

解法一: 单调栈

go

func maxResult(nums []int, k int) int {
  n := len(nums)
  dp := make([]int, n)
  dp[0] = nums[0]
  stack := []int{0}
  for i := 1; i < n; i++ {
    if stack[0] < i-k {
      stack = stack[1:]
    }
    dp[i] = nums[i] + dp[stack[0]]
    for len(stack) > 0 && dp[stack[len(stack)-1]] <= dp[i] {
      stack = stack[:len(stack)-1]
    }
    stack = append(stack, i)
  }
  return dp[n-1]
}