Skip to content

3660. Jump Game IX

Description

You are given an integer array nums.

From any index i, you can jump to another index j under the following rules:

  • Jump to index j where j > i is allowed only if nums[j] < nums[i].
  • Jump to index j where j < i is allowed only if nums[j] > nums[i].

For each index i, find the maximum value in nums that can be reached by following any sequence of valid jumps starting at i.

Return an array ans where ans[i] is the maximum value reachable starting from index i.

 

Example 1:

Input: nums = [2,1,3]

Output: [2,2,3]

Explanation:

  • For i = 0: No jump increases the value.
  • For i = 1: Jump to j = 0 as nums[j] = 2 is greater than nums[i].
  • For i = 2: Since nums[2] = 3 is the maximum value in nums, no jump increases the value.

Thus, ans = [2, 2, 3].

Example 2:

Input: nums = [2,3,1]

Output: [3,3,3]

Explanation:

  • For i = 0: Jump forward to j = 2 as nums[j] = 1 is less than nums[i] = 2, then from i = 2 jump to j = 1 as nums[j] = 3 is greater than nums[2].
  • For i = 1: Since nums[1] = 3 is the maximum value in nums, no jump increases the value.
  • For i = 2: Jump to j = 1 as nums[j] = 3 is greater than nums[2] = 1.

Thus, ans = [3, 3, 3].

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109​​​​​​​

Solutions

Solution 1: Dynamic Programming

If \(i = n - 1\), then it can jump to the maximum value in \(\textit{nums}\), so \(\textit{ans}[i] = \max(\textit{nums})\). For other positions \(i\), we can calculate by maintaining a prefix maximum array and a suffix minimum variable.

The specific steps are as follows:

  1. Create an array \(\textit{preMax}\), where \(\textit{preMax}[i]\) represents the maximum value in the interval \([0, i]\) when traversing from left to right.
  2. Create a variable \(\textit{sufMin}\), which represents the minimum value to the right of the current element when traversing from right to left. Initially \(\textit{sufMin} = \infty\).
  3. First preprocess the \(\textit{preMax}\) array.
  4. Next, traverse the array from right to left. For each position \(i\), if \(\textit{preMax}[i] > \textit{sufMin}\), it means we can jump from \(i\) to the position where \(\textit{preMax}\) is located, then jump to the position where \(\textit{sufMin}\) is located, and finally jump to \(i + 1\). Therefore, the numbers that can be reached from \(i + 1\) can also be reached from \(i\), so \(\textit{ans}[i] = \textit{ans}[i + 1]\); otherwise update to \(\textit{preMax}[i]\). Then update \(\textit{sufMin}\).
  5. Finally return the result array \(\textit{ans}\).

Time complexity \(O(n)\), space complexity \(O(n)\). Where \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        pre_max = [nums[0]] * n
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], nums[i])
        suf_min = inf
        for i in range(n - 1, -1, -1):
            ans[i] = ans[i + 1] if pre_max[i] > suf_min else pre_max[i]
            suf_min = min(suf_min, nums[i])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            preMax[i] = Math.max(preMax[i - 1], nums[i]);
        }
        int sufMin = 1 << 30;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = preMax[i] > sufMin ? ans[i + 1] : preMax[i];
            sufMin = Math.min(sufMin, nums[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        vector<int> preMax(n, nums[0]);
        for (int i = 1; i < n; ++i) {
            preMax[i] = max(preMax[i - 1], nums[i]);
        }
        int sufMin = 1 << 30;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = preMax[i] > sufMin ? ans[i + 1] : preMax[i];
            sufMin = min(sufMin, nums[i]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func maxValue(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    preMax := make([]int, n)
    preMax[0] = nums[0]
    for i := 1; i < n; i++ {
        preMax[i] = max(preMax[i-1], nums[i])
    }
    sufMin := 1 << 30
    for i := n - 1; i >= 0; i-- {
        if preMax[i] > sufMin {
            ans[i] = ans[i+1]
        } else {
            ans[i] = preMax[i]
        }
        sufMin = min(sufMin, nums[i])
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maxValue(nums: number[]): number[] {
    const n = nums.length;
    const ans = Array(n).fill(0);
    const preMax = Array(n).fill(nums[0]);
    for (let i = 1; i < n; i++) {
        preMax[i] = Math.max(preMax[i - 1], nums[i]);
    }
    let sufMin = 1 << 30;
    for (let i = n - 1; i >= 0; i--) {
        ans[i] = preMax[i] > sufMin ? ans[i + 1] : preMax[i];
        sufMin = Math.min(sufMin, nums[i]);
    }
    return ans;
}

Comments