O(n) java solution using stack


  • 1
    Z
    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            if(nums == null || nums.length == 0) return new int[0];
            int[] ret = new int[nums.length];
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            for(int i = nums.length - 2; i >= 0; i--) {
                while(!stack.isEmpty() && nums[i] >= stack.peek()) stack.pop();
                stack.push(nums[i]);
            }
            for(int i = nums.length - 1; i>= 0; i--) {
                while(!stack.isEmpty() && nums[i] >= stack.peek()) stack.pop();
                if(stack.isEmpty()) ret[i] = -1;
                else ret[i] = stack.peek();
                stack.push(nums[i]);
            }
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.