给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer
其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后
如果气温在这之后都不会升高,请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
单调递增栈:可以找到temperature[i]左侧比他小的第一个数
if(!st.empty() && st.top() > temperature[i]) st.pop()
st.push(temperature[i])
例子:3 4 2
stk[3]
stk[3 4]
stk[2]
单调递增栈
单调递减栈:可以找到temperature[i]左侧比他大的第一个数,也可以找到左侧比他小的的数
if(!st.empty() && st.top() < temperature[i]) st.pop()
st.push(temperature[i])
当St.top()<t[i]的时候,说明栈顶元素是i左侧比i小的数
class Solution {
public:
vector[HTML_REMOVED] dailyTemperatures(vector[HTML_REMOVED]& temperatures) {
int n = temperatures.size();
vector[HTML_REMOVED] ans(n);
stack[HTML_REMOVED] st;
for(int i = 0 ; i < n ; i ++){
while(!st.empty() && temperatures[st.top()] < temperatures[i]){
//栈头就是第一个比i小的元素的索引
int previousIndex = st.top();
ans[previousIndex] = i - previousIndex;
st.pop();
}
st.push(i);
}
return ans;
}
};