LeetCode 496. Next Greater Element I（下一个较大的数 I）

题目描述

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:

1. All elements in nums1 and nums2 are unique.
2. The length of both nums1 and nums2 would not exceed 1000.

解法一

思路

这个问题可以拆成两步，对于nums1中的每个元素num1：

1. 在nums2中找到num1的下标index；
2. 在nums2的(index, len(nums2))范围内找到第一个比num1大的数。

对于第1步"在nums2中找到num1的下标index"，很容易想到用Map把值映射到下标就好了。这里因为nums2中的元素一定是正数，所以可以直接用数组来模拟Map，就是拿空间换时间了。

第2步就很直接了，遍历就好了。

仔细观察还可以发现，如果nums1中的某个元素大于等于nums2中的元素最大值的话，这个元素得到的值肯定是-1，因为在nums2中不可能找到比其更大的数了。

Python

class Solution(object):
    def nextGreaterElement(self, findNums, nums):
        """
        :type findNums: List[int]
        :type nums: List[int]
        :rtype: List[int]
        """
        result = []
        if not findNums:
            return result
        num_max = max(nums)
        map = [-1] * (num_max + 1)
        for index, num in enumerate(nums):
            map[num] = index
        for find_num in findNums:
            if find_num >= num_max:
                result.append(-1)
            else:
                current_index = map[find_num] + 1
                while current_index < len(nums):
                    if nums[current_index] > find_num:
                        result.append(nums[current_index])
                        break
                    current_index += 1
                if current_index == len(nums):
                    result.append(-1)
        return result

Java

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        if (findNums.length == 0) {
            return new int[]{};
        }
        int numMax = -1;
        for (int num : nums) {
            if (num > numMax) {
                numMax = num;
            }
        }
        int[] map = new int[numMax + 1];
        for (int i = 0; i < nums.length; i++) {
            map[nums[i]] = i;
        }
        int[] result = new int[findNums.length];
        for (int i = 0; i < findNums.length; i++) {
            int currentNum = findNums[i];
            if (currentNum > numMax) {
                result[i] = -1;
            } else {
                int currentIndex = map[currentNum] + 1;
                while (currentIndex < nums.length) {
                    if (nums[currentIndex] > currentNum) {
                        result[i] = nums[currentIndex];
                        break;
                    }
                    currentIndex++;
                }
                if (currentIndex == nums.length) {
                    result[i] = -1;
                }
            }
        }
        return result;
    }
}

C++

class Solution {
public:
    vector<int> nextGreaterElement(vector<int> &findNums, vector<int> &nums) {
        vector<int> result;
        if (findNums.empty()) {
            return result;
        }
        int numMax = *max_element(nums.begin(), nums.end());
        vector<int> map(numMax + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]] = i;
        }
        for (int i = 0; i < findNums.size(); i++) {
            int currentNum = findNums[i];
            if (currentNum > numMax) {
                result.push_back(-1);
            } else {
                int currentIndex = map[currentNum] + 1;
                while (currentIndex < nums.size()) {
                    if (nums[currentIndex] > currentNum) {
                        result.push_back(nums[currentIndex]);
                        break;
                    }
                    currentIndex++;
                }
                if (currentIndex == nums.size()) {
                    result.push_back(-1);
                }
            }
        }
        return result;
    }
};