LeetCode75| 单调栈

本文主要是介绍LeetCode75| 单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

739 每日温度

901 股票价格跨度

---

739 每日温度

求后面第一个比他大的元素的位置，单调栈需要递增

求后面第一个比他小的元素的位置，单调栈需要递减

本题栈头到栈底的顺序应该从小到大

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int>st;vector<int>res(temperatures.size());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()]){res[st.top()] = i - st.top();st.pop();}st.push(i);}}return res;}
};

时间复杂度O(n)

空间复杂度O(n)

901 股票价格跨度

求后面第一个比他大的元素的位置，单调栈需要递增

求后面第一个比他小的元素的位置，单调栈需要递减

本题栈头到栈底的顺序应该从大到小

注意插入一个日期为-1，价格为INT_MAX的值，确保栈不会为空

class StockSpanner {
public:StockSpanner() {this->st.emplace(-1,INT_MAX);this->idx = -1;}int next(int price) {idx++;while(st.top().second <= price){st.pop();}int res = idx - st.top().first;st.emplace(idx,price);return res;}
private:stack<pair<int,int>>st;int idx;
};

时间复杂度O(n)

空间复杂度O(n)

这篇关于LeetCode75| 单调栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---