目标
给你一个整数数组 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
思路
有一个整数数组 nums，从任意下标 i 出发，可以向后跳到比 nums[i] 小的位置，向前跳到比 nums[i] 大的位置。返回从每一个下标 i 出发跳跃任意次能够到达的 nums 中的最大值。
定义 dp[i] 表示下标 i 所能到达的最大值，记录前缀最大值 preMax 与后缀最小值 suffixMin。如果 preMax[i + 1] <= suffixMin[i + 1]，dp[i] = preMax[i + 1]，否则 dp[i] = dp[i + 1]。
// todo: 树状数组 线段树 单调栈解法
代码
/**
* @date 2026-05-07 14:41
*/
public class MaxValue3660 {
public int[] maxValue(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int[] preMax = new int[n + 1];
for (int i = 0; i < n; i++) {
preMax[i + 1] = Math.max(preMax[i], nums[i]);
}
int suffixMin = nums[n - 1];
dp[n - 1] = preMax[n];
for (int i = n - 2; i >= 0; i--) {
if (preMax[i + 1] <= suffixMin) {
dp[i] = preMax[i + 1];
} else {
dp[i] = dp[i + 1];
}
suffixMin = Math.min(suffixMin, nums[i]);
}
return dp;
}
}
性能
