2026-01-25：跳跃游戏Ⅳ。用go语言，给出一个整数数组 nums。对于任意起点索引 i，你可以按下面的规则多次移动到其他索引： - 只能向右走

福大大架构师每日一题

发布于 2026-01-28 10:32:03

440

2026-01-25：跳跃游戏Ⅳ。用go语言，给出一个整数数组 nums。对于任意起点索引 i，你可以按下面的规则多次移动到其他索引：

• 只能向右走（到更大的下标 j>i）且目标位置的值必须比当前位置小；
• 只能向左走（到更小的下标 j<i）且目标位置的值必须比当前位置大。

对每个索引 i，求从 i 出发经过任意次符合上述限制的移动后，能够到达的元素中数值的最大值（起点也算作可达）。返回一个数组 ans，使得 ans[i] 等于从索引 i 出发能达到的最大数值。若没有任何合法移动，则 ans[i]=nums[i]。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

输入: nums = [2,1,3]。

输出: [2,2,3]。

解释:

对于 i = 0：没有跳跃方案可以获得更大的值。

对于 i = 1：跳到 j = 0，因为 nums[j] = 2 大于 nums[i]。

对于 i = 2：由于 nums[2] = 3 是 nums 中的最大值，没有跳跃方案可以获得更大的值。

因此，ans = [2, 2, 3]。

题目来自力扣3660。

算法步骤详解

1. 预处理前缀最大值

算法首先创建一个长度为n（数组长度）的preMax数组，用于存储从左到右的前缀最大值。具体过程是：

• 初始化preMax[0]为nums[0]
• 从索引i=1开始遍历到n-1，每个位置的preMax[i]取preMax[i-1]和nums[i]中的较大值
• 完成后，preMax[i]表示从数组开头到位置i之间的最大值

2. 逆向处理并更新结果

接下来算法从右向左进行第二次遍历，同时维护一个变量sufMin（后缀最小值）：

• 初始化sufMin为一个极大值（math.MaxInt）
• 从最后一个元素开始向前遍历（i = n-1到i = 0）
• 在每个位置i，检查当前的前缀最大值preMax[i]是否大于sufMin
• 如果满足条件preMax[i] > sufMin，说明存在某种跳跃路径可以到达比当前前缀最大值更大的值，此时将preMax[i]更新为preMax[i+1]
• 更新sufMin为当前sufMin和nums[i]中的较小值

3. 处理逻辑解析

这个算法的核心思想基于题目中的跳跃规则：

• 向右跳：只能跳到值更小的位置（需要当前值大于目标值）
• 向左跳：只能跳到值更大的位置（需要当前值小于目标值）

通过结合前缀最大值和后缀最小值的处理，算法能够确定从每个位置出发经过任意次跳跃后能够到达的最大值。当preMax[i] > sufMin时，意味着存在一条路径可以绕过当前限制到达更大的值。

复杂度分析

时间复杂度

• 第一次正向遍历：需要O(n)时间计算前缀最大值
• 第二次逆向遍历：需要O(n)时间更新结果
• 总时间复杂度：O(n)

空间复杂度

• 需要额外的preMax数组，长度为n
• 使用常数个辅助变量（如sufMin）
• 总空间复杂度：O(n)

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func maxValue(nums []int) []int {
    n := len(nums)
    preMax := make([]int, n)
    preMax[0] = nums[0]
    for i := 1; i < n; i++ {
        preMax[i] = max(preMax[i-1], nums[i])
    }

    sufMin := math.MaxInt
    for i := n - 1; i >= 0; i-- {
        if preMax[i] > sufMin {
            preMax[i] = preMax[i+1]
        }
        sufMin = min(sufMin, nums[i])
    }
    return preMax
}

func main() {
    nums := []int{2, 1, 3}
    result := maxValue(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def max_value(nums: List[int]) -> List[int]:
    n = len(nums)
    pre_max = [0] * n
    pre_max[0] = nums[0]
    
    # 计算前缀最大值
    for i in range(1, n):
        pre_max[i] = max(pre_max[i - 1], nums[i])
    
    suf_min = float('inf')
    
    # 从后向前遍历，根据后缀最小值更新结果
    for i in range(n - 1, -1, -1):
        if pre_max[i] > suf_min:
            # 注意：这里需要检查索引范围，避免越界
            if i < n - 1:
                pre_max[i] = pre_max[i + 1]
        suf_min = min(suf_min, nums[i])
    
    return pre_max

def main():
    nums = [2, 1, 3]
    result = max_value(nums)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<int> maxValue(const vector<int>& nums) {
    int n = nums.size();
    vector<int> preMax(n);
    preMax[0] = nums[0];

    // 计算前缀最大值
    for (int i = 1; i < n; i++) {
        preMax[i] = max(preMax[i - 1], nums[i]);
    }

    int sufMin = INT_MAX;

    // 从后向前遍历，根据后缀最小值更新结果
    for (int i = n - 1; i >= 0; i--) {
        if (preMax[i] > sufMin) {
            // 注意检查索引范围，避免越界
            if (i < n - 1) {
                preMax[i] = preMax[i + 1];
            }
        }
        sufMin = min(sufMin, nums[i]);
    }

    return preMax;
}

int main() {
    vector<int> nums = {2, 1, 3};
    vector<int> result = maxValue(nums);

    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]" << endl;

    return0;
}