leetcode739. 每日温度单调栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode739. 每日温度单调栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

自己思路：

想到用两个栈，一个维护元素、另一个维护下标。但是还是无法处理有重复元素的问题（用哈希表来存储的时候）。所以就看了答案的思路。

答案思路：

从前往后遍历，维护一个单调栈。栈存放数组的下标。

①栈为空 or 当前下标元素 <= 栈顶元素，入栈；

②当前下标元素 > 栈顶元素，就出栈，并计算它们的下标之差，存入到这个出栈元素对应的数组里面。

代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);	// 设置存放当前下标温度之后的几天可以遇到高温度
        stack<int> st;	// 单调栈，用来存放元素下标
        int i = 0;
        while( i != temperatures.size()) {
            int t = temperatures[i];  // 获取当前下标元素
            // 如果栈为空 or t<= 栈顶元素，就入栈，并把指针后移
            if(st.empty() || t <= temperatures[st.top()]){
                st.push(i);
                i++;
            }
            // 如果 t>栈顶元素，那么就是栈顶这个温度找到了比它高的温度，出栈栈顶元素并计算它们之间的间隔天数，存入到与栈顶元素相关的数组中。
            else if (t > temperatures[st.top()]) {
                int loc = st.top();
                st.pop();
                ans[loc] = i - loc;
            }
        }
        return ans;
    }
};

运行结果：

leetcode739. 每日温度单调栈,LeetCode,java,数据结构,算法