# 739 - Daily Temperatures

解法一 - Stack 解法

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> ans(T.size(), 0);

        // Use stack to store <temp, idx> pair for O(n) calculation
        stack<pair<int, int>> st;
        for(int i = 0; i < T.size(); ++i) {
            while(!st.empty() and st.top().first < T[i]) {
                pair<int, int> cur = st.top();
                st.pop();
                ans[cur.second] = i - cur.second;
            }
            st.push(make_pair(T[i], i));
        }

        return ans;
    }
};