题目
力扣：739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
题解
这道题最直观的做法就是双循环遍历数组，但是这样性能很差。
较好的办法是使用单调栈来保存尚未取得更大值的元素，在维护栈的单调性以避免重复比较。这样可以将时间复杂度降低到 $O(n)$
整体思想是：当前下标栈温度低于栈顶温度时，将该下标入栈。如果栈顶温度低于当前下标栈温度时，说明该栈顶找到更高的温度，出栈并将天数写入答案数组即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution
{
public:
std::vector<int> dailyTemperatures(std::vector<int> &temperatures)
{
std::stack<int> st;
std::vector<int> res(temperatures.size(), 0);
int i, j, n = temperatures.size();
for (i = 0; i < n; i++)
{
while (!st.empty() && temperatures[i] > temperatures[st.top()])
{
j = st.top();
st.pop();
res[j] = i - j;
}
st.push(i);
}
return res;
}
};
|
核心是理解单调栈的思想，单调栈严格递减使得栈内都是还没找到更高温度的待处理元素，栈上越靠后的元素温度越低，越容易被新元素匹配。当不断出栈，就是不断找到更高温度的过程。