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].

解題思路

簡單的說，這道題需要我們找到某個數(shù)組元素后面的最早出現(xiàn)的元素。簡單的思路就是：從這個點出發(fā)，找后面的所有點，是否有比它還要大的元素；如果出現(xiàn)了，就記錄下二者下標的差值；若沒有，則記錄下0。這是一種可取的思路，假設平均在后面的第k個點才找到符合要求的值，那么這個算法的復雜度將會是O(N * K)。k的大小取決于數(shù)據(jù)，如果這是一個從大到小排列的序列，那么K = n/2。復雜度將會是O(n^2)的規(guī)模。而題目給出的數(shù)組大小會達到30000，很顯然，這種方法是不可取的。

在上述的方法中，對每一個點，我們都遍歷了太多不符合要求的點。最好的情況是，對于每一個點，我們只需要知道它自己的值以及第一個符合要求的值即可，那么我們要如何實現(xiàn)呢？考慮用一個棧結(jié)構來存儲這個列表。對于每一個元素，我們在進棧之前，先判斷棧頂元素是否比它要小，若比它要小，則棧頂元素最早出現(xiàn)的比它自身大的元素就是當前的元素，出棧并繼續(xù)判斷；若棧頂元素不比它小，則進棧。這樣一來，每一個元素我們最多只會對它進行一次入棧和出棧的操作，這樣一來，復雜度就會由O(N * K)下降到O(2n)。而付出的代價是，多維護了一個?？臻g。

時間復雜度分析

對于每一個元素而言，最多只進行一次入棧和出棧的操作，復雜度為O(n)。

空間復雜度分析

能夠存下n個元素的棧以及返回的結(jié)果，復雜度為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;
  }
};