739. 每日温度

题目描述

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解题思路

首先，分析题型，本题的题型可以归纳为“从数组元素的左边/右边找比它更大/更小的元素”。这种“左右两边比大小”的题目都可以归类为单调栈模板题，只要熟悉单调栈相关的知识[1, 2, 3]就可以套模板解题。

简单分析下背景，单调栈的特点是，从栈底到栈顶，元素单调递增/递减。解题的关键在于定义符合题意的出栈和入栈规则，让单调栈内保存的信息可以为我所用。

结合题意，本题需要我们找到数组元素x右边的、离x最近的、而且比x还要大的元素。我们先把元素x放进栈里，然后遍历剩下来的数组。如果暂时找不到这样的元素，就可以先把遍历到的元素放进单调栈里。如果找到了这样的元素，那么就可以把栈里面的元素拿出来。

总结以上思路，不难给出符合题意的入栈出栈规则定义：

  • 如果 栈空 或 新元素比栈顶元素要小

    • 把新元素放进栈里

  • 如果 新元素比栈顶元素要大

    • 依次把符合条件的栈顶元素弹出
    • 标记解题结果
    • 最后把新元素放进栈里

本题要求的是找右侧更大的元素，反之，我们用单调栈存的就是暂时不符合要求的元素，因此单调栈是从栈底到栈顶单调递减的。

附上单调栈解题模板：

  1. stack<int> st;
  2. for (遍历这个数组)
  3. {
  4.     if (栈空 || 栈顶元素大于等于当前比较元素)
  5.     {
  6.         入栈;
  7.     }
  8.     else
  9.     {
  10.         while (栈不为空 && 栈顶元素小于当前元素)
  11.         {
  12.             栈顶元素出栈;
  13.             更新结果;
  14.         }
  15.         当前数据入栈;
  16.     }
  17. }

复杂度分析

每个元素需要从数组中被遍历一次、再从单调栈中被遍历一次，因此本题的时间复杂度为O(N)。

空间复杂度为单调栈构造的开销，复杂度为O(N)。

知识点

数组、单调栈

代码

  1. class Solution {
  2. public:
  3.     vector<int> dailyTemperatures(vector<int>& T) {
  4.         int n = T.size();
  5.         vector<int> results = vector<int>(n, 0);
  6.         ++n;
  8.         // 小技巧，数组末尾放一个大元素，让栈内元素统统弹出来
  9.         T.push_back(numeric_limits<int>::max());
  11.         // 栈内存放元素下标
  12.         stack<int> s = stack<int>();
  14.         for (int i = 0; i < n; ++i) {
  15.             // 入栈条件：栈空 或 新元素比栈顶元素要小
  16.             if (s.empty() || T[s.top()] >= T[i]) {
  17.                 s.push(i);
  18.             } else {
  19.                 // 出栈条件：新元素比栈顶元素要大
  20.                 while (!s.empty() && T[s.top()] < T[i]) {
  21.                     int topElement = s.top();
  22.                     s.pop();
  23.                     // 最后一个元素特殊处理
  24.                     results[topElement] = ((i == n - 1)
  25.                         ? 0
  26.                         : i - topElement);
  27.                 }
  28.                 s.push(i);
  29.             }
  30.         }
  31.         return results;
  32.     }
  33. };

官方版本

  1. class Solution {
  2. public:
  3.     vector<int> dailyTemperatures(vector<int>& T) {
  4.         int n = T.size();
  5.         vector<int> ans(n);
  6.         stack<int> s;
  7.         for (int i = 0; i < n; ++i) {
  8.             while (!s.empty() && T[i] > T[s.top()]) {
  9.                 int previousIndex = s.top();
  10.                 ans[previousIndex] = i - previousIndex;
  11.                 s.pop();
  12.             }
  13.             s.push(i);
  14.         }
  15.         return ans;
  16.     }
  17. };

官方题解将入栈看做必然情况，代码更加简洁。

参考资料

  1. 讲得比较浅的单调栈介绍blog
  2. OI Wiki 单调栈
  3. Leetcode刷题指南 单调栈相关
  4. C++ numeric limits