739. Daily Temperatures

[fockspaces]

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0] Example 2:

Input: temperatures = [30,40,50,60] Output: [1,1,1,0] Example 3:

Input: temperatures = [30,60,90] Output: [1,1,0]

[fockspaces]

解法一：stack 由後往前算，比較當前值和棧頂誰大， pop stack 直到 empty 結束判斷 stack.top() 更大，即找到最近更高溫度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size());
        stack<pair<int,int>> st; 
        st.push({temperatures.back(), temperatures.size() - 1});
        for(int i = temperatures.size() - 2; i >= 0; i--) {
            while(st.size() && st.top().first <= temperatures[i]) 
                st.pop();
            ans[i] = st.size() ? st.top().second - i : 0;
            st.push({temperatures[i], i});
        }
        return ans;
    }
};

[fockspaces]

解法二： DP 從後往前維護 dp 數組，紀錄最近的 target 距離 接著都以此往後跳即可 遇到 dp 值為 0，即跳出判斷

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> dp(n);
        for(int i = n - 2; i >= 0; i--) {
            int pt = i + 1;
            while(pt < n && temperatures[pt] <= temperatures[i]) {
                if(dp[pt] == 0) {pt = n; break;}
                pt += dp[pt];
            }
            dp[i] = pt != n ? pt - i : 0;
        }
        return dp;
    }
};

[fockspaces]

解法二改進：這方法簡潔不少，只要改變 dp[i] 的值就能每次都往更遠的地方走

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> dp(n, 1); dp.back() = 0;
        for(int i = n - 2; i >= 0; i--) {
            while(temperatures[i] >= temperatures[i + dp[i]]) {
                if(dp[i + dp[i]] == 0) {dp[i] = 0; break;}
                dp[i] += dp[i + dp[i]];
            }
        }
        return dp;
    }
};

[fockspaces]

Since we want to compare the future temperature, it's good to iterate list from back to front for minimize comparison times.

We need to keep track the future temperature that is potentially warmer than the current temperature. It's good to use stack since it can ensure the top one is the nearest possible candidates.

Time: O(2N), it's one path iteration, and the maximun stack pop is N. Space: O(N), will store the entire list in the worst case.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        stack = []
        for i in list(range(n))[::-1]:
            temp = temperatures[i]
            while stack and stack[-1][-1] <= temp:
                stack.pop()
            ans[i] = stack[-1][0] - i if stack else 0
            stack.append((i, temp))
        return ans

[fockspaces]

Use DP to solve problem. I forgot to jump out when comes to dp[cur_idx] = 0 case, and make TLS in the worst cases

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        dp = [0] * n
        for i in list(range(n))[::-1]:
            cur_temp = temperatures[i]
            cur_idx = i + 1
            while cur_idx < n and temperatures[cur_idx] <= cur_temp:
                if dp[cur_idx] == 0:
                    cur_idx = n
                    break
                cur_idx += dp[cur_idx]
            dp[i] = 0 if cur_idx == n else cur_idx - i
        return dp