题目

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.

解析

题目还是很好理解的。很显然如果采用循环的方式解，就增大了时间复杂度，有可能会超时。明显的说，此题就是以空间换时间，使运行效率更高。
诸如C++、Java类的高级语言都提供了key-value类型的数据结构，但是在C语言中没有。可以根据其原理简易的实现一个hash操作。
由于此题中全部是int，可以求其最大的int值max，根据此构建一个max+1的数组hashNumArr，key为nums2数组中的value，value为比其最大的最近的nums2数组中的值。即
hashNumArr[nums2[i]] = nums2[j] or -1;
j为比nums2[i]大的最近的位置，如果j找不到，则hashNumArr中的此值为-1。

代码（C语言）

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数组的最后一个值的hash值需要设置为-1，因为后面没有元素了，只能设置为-1。如果不设置的话nums1中存在最后一个值的话，则为random的一个值，报错。