Java solution only use HashMap with explanation, easy understand.


  • 0
    D

    My idea is using a hashmap to store the number and the index of this number's next larger number.
    e.g:
    nums = [ 3,2,4,1,9,7]
    from right to left, map pairs should be (7, -1), (9, -1), (1, 4), (4, 4), (2, 2), (3,2).
    (7, -1) means 7 does not have next larger number, so -1.
    (1, 4) means 1's next larger number's index is 4, namely, nums[4] is 9.
    ....
    So after create the map, we can easily get the answer by lookup it.

    public class Solution {
        public int[] nextGreaterElement(int[] findNums, int[] nums) 
        {
            
            if (nums == null || findNums == null || nums.length == 0 || findNums.length == 0) { return new int[0]; }
            
            // key is the number in nums, value is the index of its next larger number
            Map<Integer, Integer> map = new HashMap<>();
            
            // construct the map
            // last number in array, no next larger number, so -1;
            map.put(nums[nums.length - 1], -1);
            
            // traverse from right to left
            for (int i = nums.length - 1; i > 0 ; i--)
            {
                // find the first next larger number of nums[i - 1], namely nums[i]
                if (nums[i] > nums[i-1])
                {
                    map.put(nums[i - 1], i);
                }
                else
                {
                    int IdNext = map.get(nums[i]);
                    // continue to find next larger number
                    while (IdNext != -1 && nums[IdNext] < nums[i - 1])
                    {
                        IdNext = map.get(nums[IdNext]);
                    }
                    // no one exists
                    if (IdNext == -1) { map.put(nums[i - 1], -1); }
                    // find it
                    else { map.put(nums[i - 1], IdNext); }
                }
            }
            
            
            int[] res = new int[findNums.length];
            for (int i = 0; i < findNums.length; i++)
            {
                int id = map.get(findNums[i]);
                if (id == -1) { res[i] = -1; }
                else { res[i] = nums[id]; }
            }
            
            return res;
        }
    }
    

Log in to reply
 

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