代码随想录算法训练营第五十三天|739. 每日温度 496.下一个更大元素 I 503.下一个更大元素II
LeetCode 739. 每日温度
题目链接：739. 每日温度
踩坑：MD break当成continue了
思路：单调栈问题的核心就是构建并利用单调递增或递减的栈。最近遍历的元素在栈口，将每次遍历到的元素与栈口元素比较是解题过程。具体到本题就是，当天的温度与最近的温度（栈口元素）相比，如果当天温度低则入栈（栈口到栈底递增），如果当天温度高，说明最近一天的解以满足，所以弹出栈口元素，继续比较，直到栈空或较低。
代码：
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> st;vector<int> result(temperatures.size(), 0);st.push(0);for(int i = 1; i < temperatures.size(); i++){if(temperatures[i] <= temperatures[st.top()]){st.push(i);}else{while(!st.empty() && temperatures[i] > temperatures[st.top()]){result[st.top()] = i - st.top();st.pop();}st.push(i);}}return result;}
};
LeetCode 496.下一个更大元素 I
题目链接：496.下一个更大元素 I
踩坑：他喵的，i - st.top()记成了st.top() - i，虽然本题用不到，但找了半天就是没找出来
思路：与739. 每日温度的单调栈思路一致，只是题目要求不太一样，一是返回下一个更大的值，二是在为结果赋值时需要经过一些映射。
代码：
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> st;vector<int> result(nums1.size(), -1);unordered_map<int, int> map;for(int i = 0; i < nums1.size(); i++){map[nums1[i]] = i;}st.push(0);for(int i = 1; i < nums2.size(); i++){if(nums2[i] <= nums2[st.top()]) st.push(i);else{while(!st.empty() && nums2[i] > nums2[st.top()]){if(map.count(nums2[st.top()]) != 0) result[map[nums2[st.top()]]] = nums2[i];st.pop();}st.push(i);}}return result;}
};
LeetCode 503.下一个更大元素II
题目链接：503.下一个更大元素II
踩坑：成环问题想到了用取模，但具体怎么做忘了。第一次去模直接让i = i % size了，导致死循环。
思路：单调栈的思路还是没有变，只是变成了环，取模即可
代码：
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {stack<int> st;vector<int> result(nums.size(), -1);st.push(0);for(int i = 1; i < 2 * nums.size(); i++){int j = i % nums.size();if(nums[j] <= nums[st.top()]) st.push(j);else {while(!st.empty() && nums[j] > nums[st.top()]){result[st.top()] = nums[j];st.pop();}st.push(j);}}return result;}
};