class Solution {
public:
int maxResult(vector<int>& nums, int k) {
}
};
1696. 跳跃游戏 VI
给你一个下标从 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 。
示例 2：
输入：nums = [10,-5,-2,4,0,3], k = 3 输出：17 解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：
输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 输出：0
提示：
1 <= nums.length, k <= 105-104 <= nums[i] <= 104原站题解
php 解法, 执行用时: 259 ms, 内存消耗: 27.5 MB, 提交时间: 2024-02-05 09:30:03
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function maxResult($nums, $k) {
$n = count($nums);
// dp[i] 表示到达下标i的最大得分，则 dp[i] = max(dp[i-j] + nums[i]), 0 < j <= k
$dp = array_fill(0, $n, 0);
$dp[0] = $nums[0];
// 寻找左侧滑动窗口最大值
$que = array_fill(0, $n, 0);
$hh = 0; // 队头指针
$tt = -1; // 队尾指针
for ( $i = 0; $i < $n - 1; $i++ ) {
if ( $i - $que[$hh] >= $k ) {
$hh++;
}
while ( $hh <= $tt && $dp[$que[$tt]] <= $dp[$i] ) {
$tt--;
}
$tt++;
$que[$tt] = $i;
// 根据递推式得到dp[i+1]
$dp[$i+1] = $dp[$que[$hh]] + $nums[$i+1];
}
return $dp[$n-1];
}
}
golang 解法, 执行用时: 1320 ms, 内存消耗: 9.7 MB, 提交时间: 2023-08-18 15:35:53
func maxResult(nums []int, k int) int {
dp := make([]int, len(nums))
if k > len(nums) {
k = len(nums)
}
dp[0] = nums[0]
preMax := dp[0]
for i := 1; i < len(nums); i++ {
if i <= k {
dp[i] = preMax + nums[i]
if dp[i] > preMax {
preMax = dp[i]
}
} else {
if dp[i-k-1] == preMax {
preMax = max(dp[i-k : i]...)
}
dp[i] = preMax + nums[i]
if dp[i] > preMax {
preMax = dp[i]
}
}
}
return dp[len(nums)-1]
}
func max(nums ...int) (res int) {
res = nums[0]
for _, num := range nums {
if num > res {
res = num
}
}
return
}
golang 解法, 执行用时: 136 ms, 内存消耗: 10.2 MB, 提交时间: 2023-08-18 15:35:33
func maxResult(nums []int, k int) int {
n := len(nums)
// dp[i] 表示到达下标i的最大得分，则 dp[i] = max(dp[i-j] + nums[i]), 0 < j <= k
dp := make([]int, n)
dp[0] = nums[0]
// 寻找左侧滑动窗口最大值
que := make([]int, n)
hh, tt := 0, -1 // 队头、队尾指针
for i := 0; i < n - 1; i++ {
if i - que[hh] >= k {
hh++
}
for hh <= tt && dp[que[tt]] <= dp[i] {
tt--
}
tt++
que[tt] = i
// 根据递推式得到dp[i+1]
dp[i+1] = dp[que[hh]] + nums[i+1]
}
return dp[n-1]
}
python3 解法, 执行用时: 388 ms, 内存消耗: 39.9 MB, 提交时间: 2023-08-18 15:34:43
'''
1、用一个 dp 数组存到当前位置的最大得分；
2、用一个最大堆来存当前位置i 到它的前 k 个位置里的得分，dp[i]=nums[i]+heap[0][0]
注：最大堆的元素是一个元组(val,index)，val 表示得分, index表示索引，维护最大堆的大小为 k
'''
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
heap = []
heapq.heappush(heap, (-nums[0], 0))
for i in range(1, n):
if heap:
while i - heap[0][1] > k:
heapq.heappop(heap)
val = -heap[0][0]
dp[i] = nums[i] + val
heapq.heappush(heap, (-dp[i], i))
return dp[-1]
python3 解法, 执行用时: 252 ms, 内存消耗: 28 MB, 提交时间: 2023-08-18 15:33:38
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
#维持当前最大值 方法1:最大堆 方法2：单调递减队列（队首）
n = len(nums)
decQueue = [ (nums[0], 0) ] #单调递减队列
res = nums[0]
for i in range(1, n):
while decQueue and i - decQueue[0][1] > k: #扔掉左侧已经index超出范围的
decQueue.pop(0)
res = decQueue[0][0] + nums[i] #贪心，计算当前的最大结果
while decQueue and decQueue[-1][0] <= res: #维持单调递减的性质(容易错！！！一开始写成nums[i]了)
decQueue.pop(-1)
decQueue.append( (res, i) ) #其实是dp的思想和过程
return res
python3 解法, 执行用时: 388 ms, 内存消耗: 36.2 MB, 提交时间: 2023-08-18 15:33:18
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
#维护当前最大值 方法1：最大堆 方法2:单调递减队列（队首）
n = len(nums)
maxHeap = []
heapq.heapify(maxHeap)
heapq.heappush(maxHeap, (-nums[0], 0) )
res = nums[0]
for i in range(1, n):
while maxHeap and i - maxHeap[0][1] > k: #index的距离太大，以后i越来越大，top()就没用了
heapq.heappop(maxHeap)
res = -maxHeap[0][0] + nums[i]
heapq.heappush(maxHeap, (-res, i) ) #dp的思想
return res
java 解法, 执行用时: 25 ms, 内存消耗: 54.8 MB, 提交时间: 2023-08-18 15:32:35
class Solution {
public int maxResult(int[] nums, int k) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
// 构造滑动窗口的索引所对应的队列，队首至队尾的索引依次增大，但对应dp数组中的值依次降低
Deque<Integer> windowIndices = new LinkedList<>();
for (int i = 1; i < nums.length; i++) {
// 如果新的索引i所对应的元素dp[i - 1]大于队尾rear所对应的数组元素dp[rear]，就循环弹出队尾，直到新的元素i - 1能够成为队尾
// 因为dp[rear] < dp[i - 1]且rear < i - 1，只要窗口继续向右移，dp[rear]就一定会被dp[i - 1]压在下面，不会成为窗口最大元素
while (!windowIndices.isEmpty() && dp[i - 1] >= dp[windowIndices.peekLast()]) {
windowIndices.pollLast();
}
windowIndices.offerLast(i - 1);
if (windowIndices.peekFirst() < i - k) {
windowIndices.pollFirst();
}
dp[i] = dp[windowIndices.peekFirst()] + nums[i];
}
return dp[nums.length - 1];
}
}
cpp 解法, 执行用时: 180 ms, 内存消耗: 76 MB, 提交时间: 2023-08-18 15:31:33
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
int n = nums.size();
// 单调队列中的二元组即为 (f[j], j)
deque<pair<int, int>> q;
q.emplace_back(nums[0], 0);
int ans = nums[0];
for (int i = 1; i < n; ++i) {
// 队首的 j 不满足限制
while (i - q.front().second > k) {
q.pop_front();
}
ans = q.front().first + nums[i];
// 队尾的 j 不满足单调性
while (!q.empty() && ans >= q.back().first) {
q.pop_back();
}
q.emplace_back(ans, i);
}
return ans;
}
};
cpp 解法, 执行用时: 172 ms, 内存消耗: 88.5 MB, 提交时间: 2023-08-18 15:31:07
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
int n = nums.size();
// 优先队列中的二元组即为 (f[j], j)
priority_queue<pair<int, int>> q;
q.emplace(nums[0], 0);
int ans = nums[0];
for (int i = 1; i < n; ++i) {
// 堆顶的 j 不满足限制
while (i - q.top().second > k) {
q.pop();
}
ans = q.top().first + nums[i];
q.emplace(ans, i);
}
return ans;
}
};