Learner Level
Implement the nextGreaterElementArray method that returns the next greater value for each array element.
The input contains an integer array nums and its length size. For each element, your task is to find the next greater value on its right side.
If no greater value exists to the right of an element, store -1 for that position.
For example, for [2,1,2,4,3], the result is [4,2,4,-1,-1].
Example 1
Input
nums (int[]) =
[2,1,2,4,3]size (int) =
5Returns (int[])
[4,2,4,-1,-1]Example 2
Input
nums (int[]) =
[1,2,3]size (int) =
3Returns (int[])
[2,3,-1]Example 3
Input
nums (int[]) =
[3,2,1]size (int) =
3Returns (int[])
[-1,-1,-1]Use a monotonic stack of indexes whose next greater value has not been found yet.
Scan the array from left to right. While the current value is greater than the value at the index stored on top of the stack, the current value is the next greater element for that stored index.
Set those answers and pop the indexes. Push the current index so it can also wait for a future greater value.
Pseudocode:
function nextGreaterElementArray(nums, size):
result = array of size filled with -1
stack = empty stack of indexes
for i from 0 to size - 1:
while stack is not empty and nums[i] > nums[top of stack]:
index = pop from stack
result[index] = nums[i]
push i into stack
return resultReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run