Java solution with just a map and amortized O(n)


  • 0
    M
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
            int []res = new int[findNums.length];
            if (nums.length==0) return res;
            
            Map<Integer,Integer> map= new HashMap<>();
            
            map.put(nums[nums.length-1],-1);
            
            for(int i=nums.length-2;i>=0;i--){
                if (nums[i]<nums[i+1]) map.put(nums[i],nums[i+1]);
                else {
                    int a = nums[i+1];
                    while(a!=-1 && nums[i]>a){
                        a = map.get(a);
                    }
                    map.put(nums[i],a);
                }
            }
            
            int i=0;
            for(int a:findNums){
                res[i++] = map.get(a);
            }
            return res;
        }
    

Log in to reply
 

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