496. 下一个更大元素 I
这里我们采用单调栈来写这道题。
首先遍历nums2,并新开一个数组ant,存储对应nums2的下一个更大元素,这里采用单调栈,从栈顶到栈底是递增序列。
然后我们遍历a,再遍历b找到对应nums1==nums2,然后nums1存储ant里的下一个更大元素
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int stk[10005];int tt=0;vector<int>ant(nums2.size());for(int i=nums2.size()-1;i>=0;i--){while(tt&&nums2[i]>=stk[tt])tt--;if(tt)ant[i]=stk[tt];else ant[i]=-1;stk[++tt]=nums2[i];}for(int i=0;i<nums1.size();i++){for(int j=0;j<nums2.size();j++){if(nums1[i]==nums2[j]){nums1[i]=ant[j];break;}}} return nums1;}
};
503. 下一个更大元素 II
这个题涉及到循环数组,但我们可以采用单调栈的方法来处理这道题。
先从右往左遍历数组nums,进行一遍单调栈,这时栈里存的是递增序列,这时我们从右往左接着遍历,继续使用单调栈,并修改每一步nums的值即可。
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int skt[10005];int tt=0;for(int i=nums.size()-1;i>=0;i--){while(tt && nums[i]>=skt[tt])tt--;skt[++tt]=nums[i];}for(int i=nums.size()-1;i>=0;i--){while(tt&&nums[i]>=skt[tt])tt--;skt[++tt]=nums[i];if(tt>1)nums[i]=skt[tt-1];else nums[i]=-1;}return nums;}
};