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
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
Solutions
This algorithm finds the maximum value within contiguous ranges for each position in the array using a stack-based approach. It maintains a stack of objects, each tracking a value and its left-right boundaries. As it iterates through each number, if that number is smaller than the top of the stack, it can't expand further right, so it pops larger elements and merges their ranges together—expanding leftward to include what was popped. Once all elements are processed, the stack contains non-overlapping ranges where each holds the maximum value for its span. Finally, it fills the answer array by assigning each stacked value to all positions within its left-right boundaries, effectively creating an array where each position is mapped to the maximum value that dominates its local region.
/**
* @param {number[]} nums
* @return {number[]}
*/
var maxValue = function (nums) {
const n = nums.length;
const ans = new Array(n);
const stack = [];
for (let i = 0; i < n; i++) {
let curr = {
value: nums[i],
left: i,
right: i,
};
while (stack.length > 0 && stack.at(-1).value > nums[i]) {
const top = stack.pop();
curr = {
value: Math.max(curr.value, top.value),
left: top.left,
right: curr.right,
};
}
stack.push(curr);
}
for (let i = 0; i < stack.length; i++) {
for (let j = stack[i].left; j <= stack[i].right; j++) {
ans[j] = stack[i].value;
}
}
return ans;
};