739. Daily Temperatures

發表於 | 分類於

problem

solution

  • brute force so time out
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) {
            int n =temperatures.size();
            vector<int> ret(n,0);
            for(int i=0;i<n-1;++i){
                for(int j=i+1;j<n;++j){
                    if(temperatures[j] > temperatures[i]){
                        ret[i] = j-i;
                        break;
                    }
                }
            }
            return ret;
        }
    };
  • monotonic stack with index to compute number of days you have to wait after to get a warmer temperature
  • 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> sta;
            int n = temperatures.size();
            vector<int> ret(n,0);
            for(int i=0;i<n;++i){
                while(!sta.empty() && temperatures[sta.top()] < temperatures[i] ){
                    int t = sta.top();
                    sta.pop();
                    ret[t] = i-t;
                }
                sta.push(i);
            }
            return ret;
        }
    };

    analysis

  • time complexity O(n)
  • space complexity O(n)