【leetcode刷题】T25-下一个更大元素 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 = [,,], nums2 = [,,,].
Output: [-1,,-1]
Explanation:
For number in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number in the first array, the next greater number for it in the second array is 3.
For number in the first array, there is no next greater number for it in the second array, so output -1.
【中文题目】
给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
示例 1:
输入: nums1 = [,,], nums2 = [,,,].
输出: [-1,,-1]
解释:
对于num1中的数字，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字，第二个数组中数字右边的下一个较大数字是 。
对于num1中的数字，第二个数组中没有下一个更大的数字，因此输出 -1。
【思路】
第一个方法，暴力破解，遍历nums1，再遍历nums2，得到满足条件的结果，时间复杂度O(m*n)
可以降低时间吗？
能不能先遍历nums2得到所有数的greater number？当然可以。
使用栈结构，先存储nums2[0]，接着遍历数组nums2：如果遇到元素e比栈顶元素大，则存入字典，并弹出栈，直到栈没有元素或者栈顶元素大于元素e，再将元素e压入栈。（这样，字典存储的是nums2的各元素及其greater number）
最后，遍历数组nums1，从字典中得到greater number。
时间复杂度为O(m+n)
【代码】
python版本
class Solution(object):
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if len(nums2) < :
return []
# 得到下一个greater number
ls = [nums2[]]
d = {}
for n in nums2[:]:
while len(ls) > and ls[-1] < n:
d[ls.pop()] = n
ls.append(n)
# 后面没有greater number的数
while len(ls) > :
d[ls.pop()] = -1
res = []
for n in nums1:
res.append(d[n])
return res
C++版本
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
map<int, int> dict;
vector<int> res;
if(nums1.size() == or nums2.size() == )
return res;
stack<int> ls;
ls.push(nums2[]);
// 生成字典，计算greater number
for(int i=; i<nums2.size(); i++){
while(ls.size() > && ls.top() < nums2[i]){
dict[ls.top()] = nums2[i];
ls.pop();
}
ls.push(nums2[i]);
}
while(ls.size() > ){
dict[ls.top()] = -1;
ls.pop();
}
// 得到greater number
for(int i=; i<nums1.size(); i++){
res.push_back(dict[nums1[i]]);
}
return res;
}
};腾讯云开发者
