leetcode_ 739 每日温度

1. 题意

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

2. 题解

2.1 暴力

像枚举有序二元组一样，找到了就跳出循环。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n, 0);for (int i = 0;i < n - 1; ++i) {int mx = i;for (int j = i + 1;j < n; ++j) {if ( temperatures[j] > temperatures[mx]) {mx = j;break;}}ans[i] = mx - i;}return ans;}
};

2.2 单调栈

像这种左边第一个右边第一个这种问题都可以用单调栈来解决。

先说从左往右的写法。

维护一个单调非递减栈，当新加元素大于栈顶元素时，说明栈顶元素右边第一个大的元素就是当前元素。不断将小于当前元素的栈顶元素出栈，直到当前栈顶大于等于当前元素或者栈空，再将当前元素入栈。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();stack<int> s;vector<int> ans(n, 0);for (int i = 0; i < n; ++i) {while (!s.empty() && temperatures[s.top()] < temperatures[i]) {ans[s.top()] = i - s.top();s.pop();}s.push(i);}return ans;}
};

再说从右往左的写法。

从右往左有一点不同的是对相同元素的处理，当两个元素相同时，靠近左边的元素会屏蔽右边的元素。因此从右往左的写法维护的是一个严格递减的单调栈。

我们从右往左遍历数组，当栈顶元素小于等于当前元素时，不断出栈。当栈顶元素大于当前元素时，说明当前元素右边第一个大于的元素就是栈顶元素。再将当前元素入栈。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();stack<int> s;vector<int> ans(n, 0);for (int i = n - 1; ~i; --i) {while (!s.empty() &&  temperatures[i] >= temperatures[s.top()]) {s.pop();}if (!s.empty()) {ans[i] = s.top() - i;}s.push(i);}return ans;}
};

3. 参考

0x3f