二级域名建站,虚拟主机与云服务器的区别,手机app软件定制,互联网十大上市公司739. 每日温度 - 力扣#xff08;LeetCode#xff09;
思路#xff1a;使用单调栈遍历#xff0c;循环找栈中比栈顶数小的就出栈#xff0c;并且记录值。比栈顶数大的就入栈#xff0c;形成单调递增的栈
class Solution {
public:vectorint dailyTemperatures(…739. 每日温度 - 力扣LeetCode
思路使用单调栈遍历循环找栈中比栈顶数小的就出栈并且记录值。比栈顶数大的就入栈形成单调递增的栈
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {int ntemperatures.size();stackintst;vectorintans(n,0);for(int i0;in;i){//循环找栈中比栈顶数小的就出栈并且记录值。比栈顶数大的就入栈形成单调递增的栈while(!st.empty()temperatures[i]temperatures[st.top()]){ans[st.top()]i-st.top();st.pop();}st.push(i);}return ans;}
};
496. 下一个更大元素 I - 力扣LeetCode
思路同上但需要给num1做哈希映射方便找出num2的中是否存在对应的值
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { vectorintans(nums1.size(),-1);stackintst;if(nums1.size()0){return ans;}unordered_mapint,intmap;for(int i0;inums1.size();i){map[nums1[i]]i;//映射nums1的下标}st.push(0);for(int i1;inums2.size();i){while(!st.empty()nums2[i]nums2[st.top()]){if(map.count(nums2[st.top()])0){//找到比下一个更大的元素判断是否在nums1中int indexmap[nums2[st.top()]];ans[index]nums2[i];}st.pop();}st.push(i);}return ans;}
};
503. 下一个更大元素 II - 力扣LeetCode
思路同上需要使用取模运算模拟复制一个相同的数组拼接在末尾。
重点头尾相连和循环问题都可以用此方法注意入栈下标不能大于数组本身的大小
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int nnums.size();vectorintans(n,-1);stackintst;for(int i0;i2*n-1;i){//取模模拟拼接数组int xnums[i%n];//找到下一个更大的元素while(!st.empty()xnums[st.top()]){ans[st.top()]x;st.pop();}//下标不能大于nums.size()if(in){st.push(i);}}return ans;}
};
总结
单调栈单调递增是求下一个更大的元素单调递减是下一个更小的元素。单调栈就是记录之前遍历过的元素。
