NextGreaterElementIOPT [source code]

public class NextGreaterElementIOPT {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Map<Integer, Integer> m = new HashMap<>();
        // go through each element in nums and set its location in HashMap
        for (int i = 0; i < nums.length; ++i) m.put(nums[i],i); //since every element is unique, there is no need (getOrDefault)

        //scan each element in the first array    
        for (int i = 0; i < findNums.length; ++i) {
            int minIndex = -1;  //initially, set the finding index to be -1
            int index = m.get(findNums[i]); //findout the corresponding index in the second (nums) array.
            while (++index < nums.length) {
                if (nums[index] > findNums[i]) {
                    minIndex = index;
                    break;
                }
            }
            if (minIndex == -1) findNums[i] = -1;
            else findNums[i] = nums[minIndex];
        }
        return findNums;
    }

    public static void main(String[] arg) {
        NextGreaterElementIOPT tester = new NextGreaterElementIOPT();
        int[] nums1 = {4,1,2,3,5};
        int[] nums2 = {1,3,4,9,2};
        // int[] nums1 = {4,1,2};
        // int[] nums2 = {1,2,3,4};
        for (int i : tester.nextGreaterElement(nums1, nums2)) System.out.println(i);
    }
}

这个算法是别人的, 速度大概是88%左右, 算是比较快的了. 而且关键是这个算法其实比 Stack 那个算法还要好理解一些, 不需要什么key observation, 思路很直接: findNums 里面每个数直接找到在 nums 里面的位置, 然后直接向后搜索碰到看到的第一个 greater 就行了; 理论上来说这个算法的时间应该是 quadratic 的, 不知道为什么最后反而比Stack 那个快? Stack 那个肯定是没有平方的;

可能是因为测试的 case 都比较小吧, 感觉 Stack 那个应该是 linear 的啊? 奇怪了.

Problem Description

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

Hide Tags Stack
Hide Similar Problems (M) Next Greater Element II