LeetCode第496题：下一个更大元素 I
LeetCode第496题：下一个更大元素 I
问题描述
给定两个没有重复元素的数组 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。
解题思路
首先在nums数组里面找到findNums每个元素的对应位置，找不到则直接存入-1；
找到之后从下一个元素开始（对应题目描述的右边），寻找比此元素大的元素下标，找到则存入下标所指向的元素。
否则就存入-1.
这个应该是最笨的方法了。。
假设findNums和nums长度分别为m和n，则此算法时间复杂度为O(mn)，空间复杂度为O(1).
解题思路改进
这道题其实就是求nums数组每个元素右边第一个比它大的元素，不存在就是-1。
所以初始化一个map，大小与nums.size()相同，记录nums每个元素以及它右边第一个比他大的元素。
如何去寻找呢？
可以遍历nums数组，用栈的栈顶来记录每个元素temp右边的元素，直到找到一个比当前元素temp大的元素，将temp与该元素一起压入map。
如果找不到比temp大的元素，那么将temp与-1一起压入map。
当map初始化完毕后，就可以开始遍历findNums数组了。
根据findNums的元素值找到其在map中的映射，将映射依次加入vector容器即可。
假设findNums和nums长度为m和n，则时间复杂度为O(max(m,n))，空间复杂度为O(n)，空间换时间。
举例
对于例1中的nums={1,3,4,2}，先遍历nums来初始化map。
1)对于1，压入3,3比1大，1右边第一个比它大的数字找到，map[1]=3；
2)对于3，压入4,4比3大，3右边第一个比它大的数字找到，map[3]=4；
3)对于4，压入2,2比4小，2出栈。nums数组结束，4右边不存在比它大的数字，map[4]=-1；
4)对于2,2已经是nums最后一个数字，2右边不存在比它大的数字，map[2]=-1.
map初始化完成，接下来遍历findNums={4,1,2}。
1)map[findNums[0]]=map[4]=-1，-1加入vector
2)map[findNums[1]]=map[1]=3，3加入vector
3)map[findNums[2]]=map[2]=-1，-1加入vector
最后vector的结果就是{-1,3，-1}，返回这个vector即可。
C++代码
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
int size1=findNums.size();
int size2=nums.size();
vector<int> result;
int flag=-1;
int index1,index2;
for(int index1=0;index1<size1;++index1){
//每次初始化flag
flag=-1;
//找到findNums[index1]在nums中的位置index2
for(index2=0;index2<size2;++index2){
if(findNums[index1]==nums[index2])
break;
}
//找到合适数字及修改flag，跳出循环
for(;index2<size2;++index2){
if(findNums[index1]<nums[index2]){
flag=nums[index2];
break;
}
}
//根据flag确定最后结果
result.push_back(flag);
}
return result;
}
};C++代码改进
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
//m_stack存放nums中元素的右边元素
//m_map存放nums每个元素的最终结果
std::stack<int> m_stack;
map<int,int> m_map;
//遍历nums初始化m_map
for(int index=0;index<nums.size();++index){
//栈不空且当前元素大于站内元素
//栈内元素出栈并不断更新
while(!m_stack.empty() && nums[index]>m_stack.top()){
m_map[m_stack.top()]=nums[index];
m_stack.pop();
}
//栈空存入元素
m_stack.push(nums[index]);
m_map[nums[index]]=-1;
}
//遍历findNums
vector<int> result;
for(int index=0;index<findNums.size();++index){
result.push_back(m_map[findNums[index]]);
}
return result;
}
};