每日温度

题面

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

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90] 输出:[1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

分析

• 该问题即需要找到当前元素的上一个/下一个更大 / 更小元素，可以用单调递减栈（找更大元素）/ 单调递增栈（找更小元素）

• 遍历数组时弹出栈中 “无效元素”（比当前元素小 / 大的），栈顶即为目标值

• 代码实现

  class Solution {
  public:
      vector<int> dailyTemperatures(vector<int>& temperatures) {
          int n = temperatures.size();
          vector<int> res(n, 0);
          stack<int> st; // 单调递减栈，存储数组下标
          for (int i = 0; i < n; ++i) {
              // 栈不为空，且当前元素 > 栈顶元素 →
              // 栈顶元素的下一个更大元素是当前元素
              while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                  res[st.top()] = i-st.top();
                  st.pop();
              }
              st.push(i);
          }
          return res;
      }
  };

• 单调栈的另一个应用