leetcode：739. 每日温度

题目

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

示例：

  1. 输入: temperatures = [73,74,75,71,69,72,76,73]
  2. 输出: [1,1,4,2,1,1,0,0]
  1. 输入: temperatures = [30,40,50,60]
  2. 输出: [1,1,1,0]
  1. 输入: temperatures = [30,60,90]
  2. 输出: [1,1,0]

解答 & 代码

单调栈：

  1. class Solution {
  2. public:
  3.     vector<int> dailyTemperatures(vector<int>& temperatures) {
  4.         vector<int> answer(temperatures.size(), 0);        // 存放答案的数组
  5.         stack<int> s;                                                                    // 单调栈，存储下标而非元素
  6.           // 倒着遍历温度数组，存入单调栈
  7.         for(int i = temperatures.size() - 1; i >= 0; --i)
  8.         {
  9.               // 如果单调栈不为空，且栈顶存的下标对应的温度小于等于当前温度，
  10.               // 那么其存在没有意义，直接pop掉
  11.               // 因为前面有更高温度存在（即当前的温度），对于更往前的元素，这个top不可能作为其最近更大元素
  12.             while(!s.empty() && temperatures[s.top()] <= temperatures[i])
  13.                 s.pop();
  14.               // 获得下标间距：
  15.               // - 如果单调栈为空，说明往后不存在天气更高的日子，答案记为 0
  16.               // - 如果单调栈不为空，则当前栈顶下标就是下一个天气更高的日子
  17.             answer[i] = s.empty() ? 0 : s.top() - i;
  18.               // 将当前下标入栈
  19.             s.push(i);
  20.         }
  21.         return answer;
  22.     }
  23. };

复杂度分析：假设温度数组中存有 n 天的温度

  • 时间复杂度 O(n)：温度数组中的每个元素，都会进栈一次，最多出栈一次
  • 空间复杂度 O(n)：单调栈最坏情况下会存储 n 个下标， 即温度数组单调递增的情况

执行结果：

  1. 执行结果：通过
  3. 执行用时：128 ms, 在所有 C++ 提交中击败了 83.66% 的用户
  4. 内存消耗：83.1 MB, 在所有 C++ 提交中击败了 88.88% 的用户