408算法题leetcode--第26天

496. 下一个更大元素 I

题目地址：496. 下一个更大元素 I - 力扣（LeetCode）

题解思路：单调栈，如注释

时间复杂度：O(n + m)

空间复杂度：O(n)

代码:

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {// 单调栈：递增栈；存数字// 用哈希表存结果数组，用于num1输出stack<int>stk;unordered_map<int, int>mp;stk.push(nums2[0]);int size = nums2.size();for(int i = 0; i < size; i++){while(!stk.empty() && nums2[i] > stk.top()){mp[stk.top()] = nums2[i]; stk.pop();}stk.push(nums2[i]);}// 输出vector<int>ret;size = nums1.size();for(int i = 0; i < size; i++){if(!mp.count(nums1[i])){ret.emplace_back(-1);} else {ret.emplace_back(mp[nums1[i]]);}}return ret;}
};

503. 下一个更大元素 II

题目地址：503. 下一个更大元素 II - 力扣（LeetCode）

题解思路：注释

时间复杂度：O(n)

空间复杂度：O(n)

代码:

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {// 单调栈：先复制前面n-1个数到原数组的后面（用下标模拟即可），再用单调栈// 记录下标，递增栈int size = nums.size();vector<int>ret(size, -1);stack<int>stk;for(int i = 0; i < size * 2 - 1; i++){while(!stk.empty() && nums[stk.top()] < nums[i % size]){ret[stk.top()] = nums[i % size];stk.pop();}stk.push(i % size);}return ret;}
};