Welcome to Subscribe On Youtube

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}$.

  • 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;
    }
}


  • 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;
    }
};


  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions