1.题目描述
给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于num1中的数字2，第二个数组中的下一个较大数字是3。
对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。
注意:
-
nums1和nums2中所有元素是唯一的。 -
nums1和nums2的数组大小都不超过1000。
-
2.解法一：暴力法（Brute Force）
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
//暴力法 O(m*n)
int sz1 = findNums.size();//m
int sz2 = nums.size();//n
for(int i = ; i!=sz1; ++i){
int j,m = ;
//找到在nums中的位置
for(j = ; j!=sz2; ++j){
if(findNums[i]==nums[j])
break;
}
//接着从下一个位置遍历，比较并赋值
for(m = j; m!=sz2 ;++m){
if(nums[m] > findNums[i]){
res.push_back(nums[m]);
break;
}
}
//右边没有更大的数
if(m == sz2)
res.push_back(-);
}
return res;
}
private:
vector<int> res;
};
3.解法二：哈希表（数字与位置映射）
- 改进点：哈希map映射寻找位置更快，比遍历寻找要快一些。
正如解法一中所体现的，先是找到findNums中数字在nums中的位置，然后往后比较与赋相应值。
使用哈希map建立nums中数字与位置的映射，可以加速找到findNums中数字在nums中的位置。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
//建立nums中数字与位置的映射
for (int i = ; i < sz2; ++i) {
m[nums[i]] = i;
}
//寻找右边更大的数字并赋相应值
for (int i = ; i < sz1; ++i) {
res[i] = -;
int start = m[findNums[i]];
for (int j = start + ; j < sz2; ++j) {
if (nums[j] > findNums[i]) {
res[i] = nums[j];
break;
}
}
}
return res;
}
private:
int sz1 = findNums.size();
int sz2 = nums.size();
vector<int> res(sz1);
unordered_map<int,int> m;
};
4.解法三：栈和哈希表（数字与右边更大数映射）
解题思路：
理解一：这道题要解决的问题比较简单。一，找到findNums中的数字在nums中的位置；二，寻找右边第一个更大的数字。
理解二（解法三）：一，先找出在muns中每一个元素的右边更大的数字；二，判断findNums中的数字是否在nums中，然后取得相应的右边第一个更大的数字或赋值-1。思路的改变，带来解法的改变。
要点：如何利用已有的数据结构，快速解决这两个问题？
（1）先找出在muns中每一个元素的右边更大的数字：哈希表 和 栈
#生长点#
---为什么用栈来做比较更快？或者为什么这里可以用上栈结构？
举个例子： 8
用栈比较时：
）1入栈，接着扫描到3，因为3比1大，所以1——>，
）然后1出栈，3进栈，接着扫描到8，因为8比3大，所以3——>
）然后3出栈，8进栈，接着扫描到2，2不大于8，2进栈，2成为新的栈顶元素
）接着扫描到4，因为4比2大，所以2——>，然后2出栈，此时栈顶元素为8，因4不大于8，4进栈，继续扫描
）接着扫描到6，因为6比4大，所以4——>，然后4出栈，此时栈顶元素为8，因6不大于8，6进栈，继续扫描
）接着扫描到9，因为9比6大，所以6——>，然后6出栈，此时栈顶元素为8，因9比8大，——>，然后8出栈，此时栈空
）9进栈，栈只有一个元素，后面没有更大的元素了。 注：栈的特点体现在寻找 数字8 的右边第一个更大的 数字9 上面。
（2），判断findNums中的数字是否在nums中：哈希表的find()或count()函数，时间复杂度为O(1)。
注意：这里也用了哈希map，用法与解法二不同，区别在于相互映射的对象不同。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
for (int num : nums) {
//遍历栈，寻找栈中每一个元素的右边的第一个更大的数字
while (!st.empty() && st.top() < num) {
m[st.top()] = num; st.pop();
}
st.push(num);
}
for (int num : findNums) {
res.push_back(m.count(num) ? m[num] : -);
}
return res;
}
private:
stack<int> st;//注：栈可以用vector来模拟实现
unordered_map<int, int> m;
vector<int> res;
};
参考资料：
1.[LeetCode] Next Greater Element I 下一个较大的元素之一 博主Grandyang