单调栈简单习题分析

Leetcode 739

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

分析：

单调栈本身是啥？其实就是一个普通栈，但这个栈有一个特性，栈中的元素有一个特点就是单调，要不是单调递增要不就是单调递减（两者都包含相等元素情况）。

每次都要将要加入栈中的元素与栈顶元素进行比较判断，符合条件（递增或递减）就保留存入栈中，但不符合就是要进行实现题目的要求，进行相应的操作后，弹出栈顶元素，但这还没完，要继续与新的栈顶元素进行比较判断，如果符合了就将这个元素加入栈中，成为新的栈顶元素。以此类推直达全部元素都操作完成。

代码：

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int>result(temperatures.size(),0);stack<int> st;st.push(0);for(int i=1;i<temperatures.size();i++){if(temperatures[i]<temperatures[st.top()]||temperatures[i]==temperatures[st.top()]){st.push(i);}else{while(!st.empty()&&temperatures[st.top()]<temperatures[i]){result[st.top()]=i-st.top();st.pop();}st.push(i);//在判断完后加入栈中  不要遗漏}}return result;}
};