Problem description:

Given a list of daily temperatures, produce a list 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 temperatures = [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].

Solution:

The start of this idea is to walk through every element in the array. We put every element in the stack, and if we get to a new temperature that is higher than stack.top(), then we can start to pop out the elements in the stack, until stack.top() is greater than new temperature. 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        ans = [0] * len(T)
        stk = []
        for i, t in enumerate(T):
            # keep pop out element and update them in ans array
            # store the index in stk
            while stk and T[i] > T[stk[-1]]:
                prev = stk.pop()
                ans[prev] = i-prev
            stk.append(i)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;
        vector<int> res(temperatures.size(), 0);
        stk.push(0);
        int index= 1;
        while(!stk.empty() && index< temperatures.size()){
            while(!stk.empty() && temperatures[index] > temperatures[stk.top()]){
                res[stk.top()]= index-stk.top();
                stk.pop();
            }
            stk.push(index);
            index++;
        }
        return res;
    }
};

time complexity: O(n)
space complexity: O(n)

reference:
https://goo.gl/cYiBN3