Find next greater element in an array

Problem statement: given a list of numbers, for each of the number in the list, find NGE which is the next number in the list which is greater than it, if none is found, then NGE is -1.

The solution is to use stack to keep track of the number seen so far, and comparing the current number with the stack top, if current number smaller than stack top, then push the number to stack, otherwise pop up the top of stack, and set its NGE to current number.

// time complexity O(n)

public static int[] findNGE(int[] nums){

assert(nums != null);

  // store NGE indices 

int[] nge = new int[nums.length];

Stack<Integer> stack = new Stack<Integer>();

for(int i=0; i<nums.length; i++){

while(!stack.isEmpty() && nums[stack.peek()]<nums[i])

nge[stack.pop()] = i;

stack.push(i);

}

while(!stack.isEmpty())

nge[stack.pop()] = -1;

return nge;

}

// time complexity amortized O(n), right? ;)

public static int[] findNGEBackward(int[] nums){
assert(nums != null);
int len = nums.length;
int[] nge = new int[len];
nge[len-1] = -1;
for(int i=len-2; i>=0; i--){
int k = i+1;
while(k>-1 && nums[i]>=nums[k])
k = nge[k];
nge[i] = k;
}
return nge;
}