739. Daily Temperatures

739. Daily Temperatures

題意

給定一個陣列的數字 temperatures 代表每日溫度

回傳一組陣列 answer，answer[i] 代表第 i 天時要等幾天才會變溫暖

• 沒有更多的天數的話，就給0

限制

• 1 <= temperatures.length <= 10^5

• 30 <= temperatures[i] <= 100

Cases

• [1, 2, 3] ⇒ [1, 1, 0]

• [3, 2, 1] ⇒ [0, 0, 0]

• [5, 4, 3, 2, 1, 3] ⇒ [0, 0, 0, 2, 1, 0]

思考

• 只要遇到更大的數字的時候，往回填入天數

• 在回填天數之前，前面的數字會是遞減數列

  • 可以用 monotonic stack，將stack內的資料不斷pop與回填到 answer 直到遇到更大的數字，代表沒有更多數字可以填了

  • 需要同時存數字及 index 才能知道兩個數字的差別天數

Solution

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

        return ans;
    }
};

Time Complexity: O(N)，內部迴圈只會跑過前面被推入stack的元素

Space Complexity: O(N)

Optimization

• 若反著遍歷，便可以不斷往後方填入數字就好，若遇到已經填過的天數，便可以利用這個天數跳過已經填過數字的位置

  • i = 7 ⇒ [73,74,75,71,69,72,76,73] ⇒ [0,0,0,0,0,0,0,0]

  • i = 6 ⇒ [73,74,75,71,69,72,76,73] ⇒ [0,0,0,0,0,0,0,0]

  • i = 5 ⇒ [73,74,75,71,69,72,76,73] ⇒ [0,0,0,0,0,1,0,0]

  • i = 4 ⇒ [73,74,75,71,69,72,76,73] ⇒ [0,0,0,0,1,1,0,0]

  • i = 3 ⇒ [73,74,75,71,69,72,76,73] ⇒ [0,0,0,2,1,1,0,0]

  • i = 2 ⇒ [73,74,75,71,69,72,76,73] ⇒ [0,0,4,2,1,1,0,0]

    • 當往後看到 temperatures[3]較小，而 answer[3] = 2，代表後1個數字更小，便可跳過到 3 + 2 - 1的位置不檢查中間的

  • i = 1 ⇒ [73,74,75,71,69,72,76,73] ⇒ [0,1,4,2,1,1,0,0]

  • i = 0 ⇒ [73,74,75,71,69,72,76,73] ⇒ [1,1,4,2,1,1,0,0]

• worst case: [98, 30, 31, 32, 33, 99]，會產生 O(N^2)的最差時間，但可以將空間複雜度限制在 O(1)，而整體時間複雜度仍是 O(N)

• https://leetcode.com/problems/daily-temperatures/solutions/1574831/java-2-simple-approaches-constant-space-or-stack-beats-100-tc-o-n-sc-o-1