文章目录

• 每日温度
• 下一个更大元素
• 下一个最大的元素II

每日温度

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

单调栈主要解决寻找数组中下一个比它大的元素的值或者下标。

单调栈问题的结果数组要先初始化，初始化的值为后面没有找到该元素的时候，该位置的值。遍历数组，每一次判断当前元素与栈顶元素的大小。

如果当前元素比栈顶元素小或者等于栈顶元素，直接进行入栈。

如果当前元素比栈顶元素大，则出栈，并循环比较，直到栈为空或者当前元素比栈顶元素小，然后当前元素入栈。

在栈顶元素出栈的时候，则当前元素就是下一个比它大的元素，并且知道栈顶元素的下标，就可以根据要求来进行求解了。

class Solution {
public:vector dailyTemperatures(vector& temperatures) {stack Monotone_Stack;vector result;result.resize(temperatures.size());for(int i=0;itemperatures[Monotone_Stack.top()]){int temp=Monotone_Stack.top();result[temp]=i-Monotone_Stack.top();Monotone_Stack.pop();}Monotone_Stack.push(i);}}while(!Monotone_Stack.empty()){result[Monotone_Stack.top()]=0;Monotone_Stack.pop();}return result;}
};

下一个更大元素

496. 下一个更大元素 I

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] 是如上所述的 下一个更大元素 。

本题也使用单调栈来进行解决，即为nums2数组来建立单调栈。

在为nums2数组建立单调栈之前，使用map结构将nums1数组保存起来，它的first是数据，它的second是下标，下标的作用是找到它在结果数组中的位置。使用map结构的好处是查找起来方便，因为vector没有find函数。

建立单调栈的时候，当发生出栈时，判断栈顶元素是否在map中，如果在则执行对应的操作，如果不在则跳过。

class Solution {
public:vector nextGreaterElement(vector& nums1, vector& nums2) {map map;stack stack;vector result;result.resize(nums1.size(),-1);for(int i=0;inums2[stack.top()]){if(map.count(nums2[stack.top()])>0){result[map[nums2[stack.top()]]]=nums2[i];}stack.pop();}stack.push(i);}}return result;}
};

下一个最大的元素II

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1

这里相当于首尾相接了，直接在原来数组再接一个相同的数组即可。

class Solution {
public:vector nextGreaterElements(vector& nums) {stack stack;vector result;nums.insert(nums.end(),nums.begin(),nums.end());  result.resize(nums.size(),-1);for(int i=0;i=nums[i]){stack.push(i);}else{while(!stack.empty()&&nums[i]>nums[stack.top()]){result[stack.top()]=nums[i];stack.pop();}stack.push(i);}}result.resize(result.size()/2);return result;}
};