題目

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.

解析

題目還是很好理解的。很顯然如果采用循環(huán)的方式解，就增大了時(shí)間復(fù)雜度，有可能會(huì)超時(shí)。明顯的說(shuō)，此題就是以空間換時(shí)間，使運(yùn)行效率更高。
諸如C++、Java類的高級(jí)語(yǔ)言都提供了key-value類型的數(shù)據(jù)結(jié)構(gòu)，但是在C語(yǔ)言中沒(méi)有?？梢愿鶕?jù)其原理簡(jiǎn)易的實(shí)現(xiàn)一個(gè)hash操作。
由于此題中全部是int，可以求其最大的int值max，根據(jù)此構(gòu)建一個(gè)max+1的數(shù)組hashNumArr，key為nums2數(shù)組中的value，value為比其最大的最近的nums2數(shù)組中的值。即
hashNumArr[nums2[i]] = nums2[j] or -1;
j為比nums2[i]大的最近的位置，如果j找不到，則hashNumArr中的此值為-1。

代碼（C語(yǔ)言）

int* nextGreaterElement(int* nums1, int nums1Size, int* nums2,
                        int nums2Size, int* returnSize){
    if (nums1 == NULL || nums1Size == 0 || nums2 == NULL || nums2Size == 0) {
        (*returnSize) = 0;
        
        return NULL;
    }
    
    (*returnSize) = nums1Size;
    
    // find the max of nums2
    int maxNum = -1;
    
    for (int i = 0; i < nums2Size; ++i) {
        if (maxNum < nums2[i])
            maxNum = nums2[i];
    }
    
    // construct the hash
    int* hashNumArr = (int*)malloc((maxNum + 1) * sizeof(int));
    
    for (int i = 0; i < nums2Size - 1; ++i) {
        hashNumArr[nums2[i]] = -1;
        
        for (int j = i; j < nums2Size; ++j) {
            if (nums2[j] > nums2[i]) {
                hashNumArr[nums2[i]] = nums2[j];
                
                break;
            }
        }
    }
    
    hashNumArr[nums2[nums2Size - 1]] = -1;
    
    int* returnArr = (int*)malloc((*returnSize) * sizeof(int));
    
    for (int i = 0; i < (*returnSize); ++i) {
        returnArr[i] = hashNumArr[nums1[i]];
    }
    
    return returnArr;
}

需要注意的是nums2數(shù)組的最后一個(gè)值的hash值需要設(shè)置為-1，因?yàn)楹竺鏇](méi)有元素了，只能設(shè)置為-1。如果不設(shè)置的話nums1中存在最后一個(gè)值的話，則為random的一個(gè)值，報(bào)錯(cuò)。