Jump Game IX
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]From index 1 you can jump to index 0 and reach value 2, while indices 0 and 2 cannot reach any higher value, so
ans = [2, 2, 3].Example 2
Input
nums = [2,3,1]Output
[3,3,3]Index 0 can reach index 2 and then index 1, index 1 already has the maximum value, and index 2 can jump to index 1, so
ans = [3, 3, 3].Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9