本文主要是介绍代码随想录算法训练营第六十一天|739. 每日温度、496.下一个更大元素 I,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
单调栈
文章目录
- 一、每日温度
- 二、下一个更大元素 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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!