代码随想录算法训练营第五十八天|LeetCode739 每日温度、LeetCode496 下一个更大的元素

本文主要是介绍代码随想录算法训练营第五十八天|LeetCode739 每日温度、LeetCode496 下一个更大的元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

739.每日温度

思路：一开始想到了两层for循环的暴力解法，没想到单调栈要干嘛，直接看题解。单调栈内存放数组索引，栈内顺序为数组值从小到大，因此栈顶的索引对应的数组值在栈内是最小的。遍历数组每个元素，如果当前元素大于栈顶的元素，直接将栈顶索引对应的result处赋值为循环当前索引i与栈顶元素st.top()的差值，然后将栈顶弹出，如果当前元素仍大于栈顶元素对应的数组值，重复上述操作。如果当前索引对应的数组值小于等于栈顶元素对应的数组值，将当前索引放入栈内。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(),-1);unordered_map<int,int> m2;stack<int> st;st.push(0);for(int i =1;i<nums2.size();i++){while(!st.empty()&&nums2[i]>nums2[st.top()]){m2[nums2[st.top()]] = nums2[i];st.pop();}st.push(i);}for(int j = 0;j<nums1.size();j++){if(m2.find(nums1[j])!=m2.end()){result[j] = m2[nums1[j]];}}return result;}
};

496.下一个更大的元素

思路：这道题分了两个数组，但本质上还是利用单调栈寻找比当前元素大的最近的那个元素。因此先对nums2寻找每个元素后面对应的最近的比他大的元素值，因此建立unordered_map<int> m2. m2[nums2[st.top()]]=nums2[i].遍历完数组2后，建立与数组1长度相同的result，遍历数组1，在m2中寻找有没有和数组1相同的元素，如果有，在对应result的位置放入map[nums1[i]]的key值。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(),-1);unordered_map<int,int> m2;stack<int> st;st.push(0);for(int i =1;i<nums2.size();i++){while(!st.empty()&&nums2[i]>nums2[st.top()]){m2[nums2[st.top()]] = nums2[i];st.pop();}st.push(i);}for(int j = 0;j<nums1.size();j++){if(m2.find(nums1[j])!=m2.end()){result[j] = m2[nums1[j]];}}return result;}
};