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

因为我们所要找的是距离最近的较大的，因此，我们从后往前，依次将索引加入到stack中，不同点在于，只要遍历到比当前栈顶元素大的，就将栈顶元素从栈中删除——因为此时栈顶元素已经不是后面的元素所距离的最近的一个，较大的元素了。因此，栈顶的元素所保存的，一直都是目前来说，索引值最小的当前最大元素的索引。因此，利用这种办法，直接从后往前就可以分别对这些距离进行计算了。

从后往前，如果当前i对应的元素大于stack的top那么就pop掉这个top，一直循环，最后stack要么为空，要么不为空，为空，则为0，不为空则为top对应的i-top减去当前i
When i = 7, stack = [7 (73)]. ans[i] = 0.
When i = 6, stack = [6 (76)]. ans[i] = 0.
When i = 5, stack = [5 (72), 6 (76)]. ans[i] = 1.
When i = 4, stack = [4 (69), 5 (72), 6 (76)]. ans[i] = 1.
When i = 3, stack = [3 (71), 5 (72), 6 (76)]. ans[i] = 2.
When i = 2, stack = [2 (75), 6 (76)]. ans[i] = 4.
When i = 1, stack = [1 (74), 2 (75), 6 (76)]. ans[i] = 1.
When i = 0, stack = [0 (73), 1 (74), 2 (75), 6 (76)]. ans[i] = 1.

如果对于这类，到当前元素最近XX等的问题，利用栈的先进后出的性质来进行求解是一种比较可取的办法。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res (n, 0);
        stack<int> s;
        for(int i = n-1;i>=0;i--)
        {
            while(!s.empty() && temperatures[i] >= temperatures[s.top()])
                s.pop();
            if(!s.empty())  res[i] = s.top() - i;
            s.push(i);
        }
        return res;
    }
};