Description Link to heading

739.dail-temperatures

Solution Link to heading

We can consider monotone stack. If the stack is empty or the element to deal with is smaller than the element in the top of the stack, we can push the element to the stack, else we should pop the element in the top of the stack until the stack is empty or the element is smaller than the element in the top of the stack.

It’s convenient to push the index i into the stack.

Code Link to heading 

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