单调栈
Question
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
单调栈
只要是这类问题，找下一个最小，就可以使用单调栈。
举个栗子
list = [1,6,4,2,5]
对应每个数的下一个更大元素
| list | 1 | 6 | 4 | 2 | 5 |
|---|---|---|---|---|---|
| ans | 6 | -1 | 5 | 5 | -1 |
单调栈就可以得到ans数组啦。
把list逆序依次放入stack中
放5时
stack = []
因为stack为空，所以没有元素比5大，此时ans[4] = -1
再把5入栈
放2时
stack = [5]
因为栈顶元素5>2，直接ans[3] = 5
再把2入栈
放4时
stack = [5,2]
4>栈顶元素2，让2出栈
此时 stack = [5]
4<栈顶元素5，直接ans[2] = 5
再把4入栈
放6时
stack = [5,4]
因为6大于栈顶元素4
4出栈
因为6大于栈顶元素5
5出栈
stack = []
栈空，所以6没有更大的元素，ans[1] = -1
把6压入栈
…
以上就是单调栈的全部了
Answer
BF
暴力法
时间复杂度O(n^2)
空间复杂度O(1)
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector <int> ans;
ans.reserve(nums1.size());
int j=0;
for(int &a:nums1){
for(j=0;j<nums2.size();j++){
if(nums2[j]==a){
for(;j<nums2.size();j++){
if(nums2[j]>a){
ans.push_back(nums2[j]);
break;
}
}
if(j==nums2.size())ans.push_back(-1);
}
}
}
return ans;
}
};单调栈
利用hash表事先一次遍历，把num2数组的下一个更大找出来。
然后遍历num1，依次再hash表里查询即可。
时间复杂度O(n+m)，空间复杂度O(m),m是num2的长度，n是num1的长度。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int>s;
unordered_map<int,int> hash;
vector<int>ans;
ans.reserve(nums1.size());
for(int i=nums2.size()-1;i>-1;i--){
while(!s.empty()&&nums2[i]>=s.top()){
s.pop();
}
hash[nums2[i]]= s.empty()?-1:s.top();
s.push(nums2[i]);
}
for(int&a:nums1){
ans.push_back(hash[a]);
}
return ans;
}
};