1696. 跳跃游戏 VI

原创

Michel_Rolle

修改于 2023-12-20 08:06:21

1.1K2

修改于 2023-12-20 08:06:21

文章被收录于专栏：golang分享golang分享

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的得分为经过的所有数字之和。

请你返回你能得到的最大得分。

示例 1：

输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。

func maxResult(nums []int, k int) int {
    q, n := make([]int, 0), len(nums)
    push := func(i int) {
        for len(q) > 0 && nums[q[len(q)-1]]  < nums[i] {
            q = q[:len(q)-1]
        }
        q = append(q, i)
    }
    push(0)
    for i := 1; i < n; i++ {
        for q[0] < i-k {
            q = q[1:] // 剔除索引超出范围k的队首元素
        }
        nums[i] += nums[q[0]] // 原地更新
        push(i)
    }
    return nums[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

锁