Java beats 97% O(n) with stack(updated)


  • 0
    F
    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            if(nums == null || nums.length == 0) {
                return nums;
            }
            if(nums.length == 1) {
                nums[0] = -1;
                return nums;
            }
            Deque<Integer> dq = new ArrayDeque<Integer>();
            int max = Integer.MIN_VALUE;
            for(int i = nums.length - 1; i >= 0; i--) {
                max = Math.max(nums[i], max);
                if(i != nums.length - 1) {
                    dq.addLast(nums[i]);
                }
            }
            int[] res = new int[nums.length];
            for(int i = nums.length - 1; i >= 0; i--) {
                int cur = nums[i];
                if(cur == max){
                    dq.addLast(cur);
                    res[i] = -1;
                } else{
                    while(!dq.isEmpty() && cur >= dq.getLast()) {
                        dq.removeLast();
                    } 
                    res[i] = dq.getLast();
                    dq.addLast(cur);
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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