739. Daily Temperatures

题目描述

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

解题思路

简单的说，这道题需要我们找到某个数组元素后面的最早出现的元素。简单的思路就是：从这个点出发，找后面的所有点，是否有比它还要大的元素；如果出现了，就记录下二者下标的差值；若没有，则记录下0。这是一种可取的思路，假设平均在后面的第k个点才找到符合要求的值，那么这个算法的复杂度将会是O(N * K)。k的大小取决于数据，如果这是一个从大到小排列的序列，那么K = n/2。复杂度将会是O(n^2)的规模。而题目给出的数组大小会达到30000，很显然，这种方法是不可取的。

在上述的方法中，对每一个点，我们都遍历了太多不符合要求的点。最好的情况是，对于每一个点，我们只需要知道它自己的值以及第一个符合要求的值即可，那么我们要如何实现呢？考虑用一个栈结构来存储这个列表。对于每一个元素，我们在进栈之前，先判断栈顶元素是否比它要小，若比它要小，则栈顶元素最早出现的比它自身大的元素就是当前的元素，出栈并继续判断；若栈顶元素不比它小，则进栈。这样一来，每一个元素我们最多只会对它进行一次入栈和出栈的操作，这样一来，复杂度就会由O(N * K)下降到O(2n)。而付出的代价是，多维护了一个栈空间。

时间复杂度分析

对于每一个元素而言，最多只进行一次入栈和出栈的操作，复杂度为O(n)。

空间复杂度分析

能够存下n个元素的栈以及返回的结果，复杂度为O(n)。

源码

class Solution {
public:
  vector<int> dailyTemperatures(vector<int>& T) {
    stack<int> Tstack;
    map<int, int> next;
    for (int i = 0; i < T.size(); ++i) {
      if (Tstack.empty()) {
        Tstack.push(i);
      } else {
        while (!Tstack.empty()) {
          int topIndex = Tstack.top();
          if (T[i] > T[topIndex]) {
            Tstack.pop();
            next[topIndex] = i - topIndex;
          } else {
            break;
          }
        }
        Tstack.push(i);
      }
    }
    while (!Tstack.empty()) {
      next[Tstack.top()] = 0;
      Tstack.pop();
    }
    vector<int> result;
    for (int i = 0; i < T.size(); ++i) {
      result.push_back(next[i]);
    }
    return result;
  }
};