3660. Jump Game IX
Medium23.8% acceptance16,739 / 70,208 submissions
Asked by 1 company
Topics
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
jwherej > iis allowed only ifnums[j] < nums[i]. - Jump to index
jwherej < iis allowed only ifnums[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 toj = 0asnums[j] = 2is greater thannums[i]. - For
i = 2: Sincenums[2] = 3is the maximum value innums, 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 toj = 2asnums[j] = 1is less thannums[i] = 2, then fromi = 2jump toj = 1asnums[j] = 3is greater thannums[2]. - For
i = 1: Sincenums[1] = 3is the maximum value innums, no jump increases the value. - For
i = 2: Jump toj = 1asnums[j] = 3is greater thannums[2] = 1.
Thus, ans = [3, 3, 3].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Hints
Hint 1
Think of the array as a directed graph where edges represent valid jumps.
Hint 2
From index
i, forward jumps go only to smaller values; backward jumps go only to larger values.Hint 3
The maximum reachable value from
i is the maximum value in the connected component reachable under these jump rules.Hint 4
You can find connected ranges by looking at prefix maximums and suffix minimums, a cut happens where all values to the left are <= all values to the right.