clean JAVA O(N) solution win 95% with only hashmap


  • 0
    W
    1. first build a hashmap for NUMS from right to left. the rightest one's value is -1;
    2. if left is smaller than direct right, save right as value in hashmap.
    3. else compare left with right = hashmap.get(right) until it is -1 or right bigger than left
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
            if(nums.length==0) return findNums;
            HashMap<Integer,Integer> m = new HashMap<>();
            m.put(nums[nums.length-1],-1);
            for(int i=nums.length-2;i>=0;i--){
                if(nums[i]<nums[i+1]){
                    m.put(nums[i],nums[i+1]);
                }else{
                    int you = m.get(nums[i+1]);
                    while(nums[i]>you&&you!=-1)
                        you = m.get(you);
                    m.put(nums[i],you);
                }
            }
            for(int i=0;i<findNums.length;i++)
                findNums[i] = m.get(findNums[i]);
            return findNums;
        }
    

Log in to reply
 

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