Problem
You are given a 0-indexed array of non-negative integers nums
. For each integer in nums
, you must find its respective second greater integer.
The second greater integer of nums[i]
is nums[j]
such that:
j > i
nums[j] > nums[i]
There exists exactly one index
k
such thatnums[k] > nums[i]
andi < k < j
.
If there is no such nums[j]
, the second greater integer is considered to be -1
.
- For example, in the array
[1, 2, 4, 3]
, the second greater integer of1
is4
,2
is3
, and that of3
and4
is-1
.
Return** an integer array answer
, where answer[i]
is the second greater integer of nums[i]
.**
Example 1:
Input: nums = [2,4,0,9,6]
Output: [9,6,6,-1,-1]
Explanation:
0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2.
1st index: 9 is the first, and 6 is the second integer greater than 4, to the right of 4.
2nd index: 9 is the first, and 6 is the second integer greater than 0, to the right of 0.
3rd index: There is no integer greater than 9 to its right, so the second greater integer is considered to be -1.
4th index: There is no integer greater than 6 to its right, so the second greater integer is considered to be -1.
Thus, we return [9,6,6,-1,-1].
Example 2:
Input: nums = [3,3]
Output: [-1,-1]
Explanation:
We return [-1,-1] since neither integer has any integer greater than it.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 109
Solution
/**
* @param {number[]} nums
* @return {number[]}
*/
var secondGreaterElement = function(nums) {
var res = Array(nums.length).fill(-1);
var stack1 = []; // first greater integer
var stack2 = []; // second greater integer
for (var i = 0; i < nums.length; i++) {
while (stack2.length && nums[i] > nums[stack2[stack2.length - 1]]) {
res[stack2.pop()] = nums[i];
}
var tempArr = [];
while (stack1.length && nums[i] > nums[stack1[stack1.length - 1]]) {
tempArr.unshift(stack1.pop());
}
stack2.push(...tempArr);
stack1.push(i);
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).