3981 Jump Game Ix

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 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​​​​​​​

impl Solution {
    pub fn max_value(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();

        let mut ans = vec![0; n];

        struct Item {
            value: i32,
            left: usize,
            right: usize,
        }

        let mut stack: Vec<Item> = Vec::new();

        for i in 0..n {
            let mut curr = Item {
                value: nums[i],
                left: i,
                right: i,
            };

            while let Some(top) = stack.last() {
                if top.value > nums[i] {
                    let top = stack.pop().unwrap();
                    curr.value = curr.value.max(top.value);
                    curr.left = top.left;
                } else {
                    break;
                }
            }

            stack.push(curr);
        }

        for i in 0..stack.len() {
            for j in stack[i].left..=stack[i].right {
                ans[j] = stack[i].value;
            }
        }

        ans
    }
}