Medium

题目描述

给定一个整数数组 nums。

从任意索引 i，你可以按照以下规则跳转到另一个索引 j：

  • 只有当 nums[j] < nums[i] 时，才允许跳转到索引 j，其中 j > i（向前跳跃）
  • 只有当 nums[j] > nums[i] 时，才允许跳转到索引 j，其中 j < i（向后跳跃）

对于每个索引 i，找到从索引 i 开始，通过任何有效跳跃序列可以到达的 nums 中的最大值。

返回一个数组 ans，其中 ans[i] 是从索引 i 开始可以到达的最大值。

示例 1:

输入：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]

示例 2:

输入：nums = [2,3,1]
输出：[3,3,3]
解释：
- 对于 i = 0：向前跳到 j = 2，因为 nums[j] = 1 < nums[i] = 2，然后从 i = 2 跳到 j = 1，因为 nums[j] = 3 > nums[2]
- 对于 i = 1：因为 nums[1] = 3 是 nums 中的最大值，没有跳跃能增加数值
- 对于 i = 2：跳到 j = 1，因为 nums[j] = 3 > nums[2] = 1
因此，ans = [3, 3, 3]

约束条件:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这道题可以理解为一个有向图的连通性问题。关键观察是：根据跳跃规则，某些位置之间会形成连通的区域，同一区域内的所有位置都能到达该区域的最大值。

核心思路：

  1. 将数组看作有向图，边表示有效跳跃
  2. 从位置 i 向前只能跳到更小的值，向后只能跳到更大的值
  3. 每个连通分量内的所有点都能到达该分量的最大值

关键洞察： 通过前缀最大值和后缀最小值可以找到分割点。当某个位置的前缀最大值小于等于该位置右侧所有元素的最小值时，就形成了一个分割，左右两边无法相互到达。

算法步骤：

  1. 计算前缀最大值数组 prefixMax
  2. 计算后缀最小值数组 suffixMin
  3. 找到所有分割点：prefixMax[i] <= suffixMin[i+1]
  4. 对每个连通区间，该区间内所有位置的答案都是区间最大值

这种方法避免了复杂的图遍历，时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        
        // 计算前缀最大值
        vector<int> prefixMax(n);
        prefixMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixMax[i] = max(prefixMax[i-1], nums[i]);
        }
        
        // 计算后缀最小值
        vector<int> suffixMin(n);
        suffixMin[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMin[i] = min(suffixMin[i+1], nums[i]);
        }
        
        // 找到连通区间并填充结果
        int start = 0;
        for (int i = 0; i < n; i++) {
            // 检查是否是分割点
            if (i == n-1 || prefixMax[i] <= suffixMin[i+1]) {
                // 计算当前区间的最大值
                int maxVal = nums[start];
                for (int j = start; j <= i; j++) {
                    maxVal = max(maxVal, nums[j]);
                }
                // 填充当前区间的结果
                for (int j = start; j <= i; j++) {
                    result[j] = maxVal;
                }
                start = i + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        
        # 计算前缀最大值
        prefix_max = [0] * n
        prefix_max[0] = nums[0]
        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i-1], nums[i])
        
        # 计算后缀最小值
        suffix_min = [0] * n
        suffix_min[n-1] = nums[n-1]
        for i in range(n-2, -1, -1):
            suffix_min[i] = min(suffix_min[i+1], nums[i])
        
        # 找到连通区间并填充结果
        start = 0
        for i in range(n):
            # 检查是否是分割点
            if i == n-1 or prefix_max[i] <= suffix_min[i+1]:
                # 计算当前区间的最大值
                max_val = max(nums[start:i+1])
                # 填充当前区间的结果
                for j in range(start, i+1):
                    result[j] = max_val
                start = i + 1
        
        return result

public class Solution {
    public int[] MaxValue(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        
        // 计算前缀最大值
        int[] prefixMax = new int[n];
        prefixMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixMax[i] = Math.Max(prefixMax[i-1], nums[i]);
        }
        
        // 计算后缀最小值
        int[] suffixMin = new int[n];
        suffixMin[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMin[i] = Math.Min(suffixMin[i+1], nums[i]);
        }
        
        // 找到连通区间并填充结果
        int start = 0;
        for (int i = 0; i < n; i++) {
            // 检查是否是分割点
            if (i == n-1 || prefixMax[i] <= suffixMin[i+1]) {
                // 计算当前区间的最大值
                int maxVal = nums[start];
                for (int j = start; j <= i; j++) {
                    maxVal = Math.Max(maxVal, nums[j]);
                }
                // 填充当前区间的结果
                for (int j = start; j <= i; j++) {
                    result[j] = maxVal;
                }
                start = i + 1;
            }
        }
        
        return result;
    }
}

var maxValue = function(nums) {
    const n = nums.length;
    const ans = new Array(n);
    const memo = new Array(n).fill(-1);
    
    function dfs(i) {
        if (memo[i] !== -1) return memo[i];
        
        let maxVal = nums[i];
        
        // Jump forward: j > i and nums[j] < nums[i]
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[i]) {
                maxVal = Math.max(maxVal, dfs(j));
            }
        }
        
        // Jump backward: j < i and nums[j] > nums[i]
        for (let j = i - 1; j >= 0; j--) {
            if (nums[j] > nums[i]) {
                maxVal = Math.max(maxVal, dfs(j));
            }
        }
        
        return memo[i] = maxVal;
    }
    
    for (let i = 0; i < n; i++) {
        ans[i] = dfs(i);
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要三次遍历数组：计算前缀最大值、后缀最小值和处理连通区间
空间复杂度O(n) - 需要额外的数组存储前缀最大值、后缀最小值和结果数组