一、题目

提示：

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• nums1和nums2中所有整数 互不相同
• nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

二、思路

单调栈就是用于解决 Next Greater Number 问题。

单调栈模板如下，首先下面版本的前提条件（可灵活改动）是找出nums数组中每个元素，对应的右边的第一个更大的元素值。我们利用一个辅助栈stack，从nums数组的最右边开始倒着遍历：

（1）每遍历到当前的元素A，将其和栈顶元素值比较大小，如果栈顶元素值小（矮子去掉）则pop掉，直到出现一个比A大的栈顶元素B；
（2）B即当前元素的res值。
（3）将A入栈，循环以上操作。

vector<int> nextGreaterElement(vector<int>& nums) {vector<int> res(nums.size()); // 存放答案的数组stack<int> s;// 倒着往栈里放for (int i = nums.size() - 1; i >= 0; i--) {// 判定个子高矮while (!s.empty() && s.top() <= nums[i]) {// 矮个起开，反正也被挡着了。。。s.pop();}// nums[i] 身后的 next great numberres[i] = s.empty() ? -1 : s.top();// s.push(nums[i]);}return res;
}

时间复杂度分析：虽然for内嵌套while循环，但是时间复杂度不是 O ( n 2 ) O(n^2) O(n2)，而是$O(n)$，因为从整理看，n个元素每个元素都被push入栈一次，最多也会被pop出栈一次，总体计算规模和元素个数n成正比。

而本题就可以直接对nums2用单调栈模板，因为nums1是nums2的子集，去后者得到的答案里找就行。
具体的找法：nums2每个元素的答案都记录在res1里，为了方便nums1直接获取，借助一个哈希表map。

三、代码

方法一：暴力两层for循环（显然时间效率很低）。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int>ans;bool flag = false;for(int i = 0; i < nums1.size(); i++){int num = nums1[i];for(int j = 0; j < nums2.size(); j++){if(nums2[j] == num){flag = true;//continue;}if(flag && nums2[j] > num){ans.push_back(nums2[j]);break;}else if(j == nums2.size()-1 && nums2[j] <= num){ans.push_back(-1);break;}}num = 0;flag = false;}return ans;}
};

方法二：单调栈

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> res1(nums2.size());vector<int> res2;map<int, int>mp;stack<int>s;for(int i = nums2.size() - 1; i >= 0; i--){while(!s.empty() && s.top() <= nums2[i]){//把矮个子全部去掉s.pop();}res1[i] = s.empty()? -1: s.top();mp.insert(make_pair(nums2[i], res1[i]));s.push(nums2[i]);}for(int j = 0; j < nums1.size(); j++){res2.push_back(mp[nums1[j]]);}return res2;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！