代码随想录算法训练营第六十一天|739. 每日温度、496.下一个更大元素 I

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

单调栈

---

一、每日温度

1.暴力解法，双层循环
2.单调栈，递增排列，分三种情况。1.当前元素大于栈顶元素，得到结果，弹出并压入。2.当前元素小于等于栈顶元素，压入栈

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {//暴力解法，双层循环stack<int>st;st.push(0);vector<int>result(temperatures.size(), 0);for (int i = 1; i < temperatures.size(); i++) {if (temperatures[i] < temperatures[st.top()]) {st.push(i);}else 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;}
};

二、下一个更大元素 I

1.暴力解法，双层循环
2.单调栈，map哈希记录nums1出现的元素，nums2使用单调栈类似于每日温度，当出现大于情况是，判断栈顶元素是否出现在map中，是则获取结果，弹出栈。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {//暴力解法，一层遍历num1，一层遍历vector<int>result(nums1.size(), -1);for (int i = 0; i < nums1.size(); i++) {int flag = 0;for (int j = 0; j < nums2.size(); j++) {if (nums2[j] == nums1[i]) {flag = j;break;};}for (int k = flag; k < nums2.size(); k++) {if (nums2[k] > nums2[flag]) {result[i] = nums2[k];break;}}}return result;}
};

---

总结

单调栈有助于降低时间复杂度
学习时间90min。
学习资料：《代码随想录》。

这篇关于代码随想录算法训练营第六十一天|739. 每日温度、496.下一个更大元素 I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---