Java

  • import java.util.Arrays;
    import java.util.Stack;
    
    /**
    
     Given a list of daily temperatures, produce a list that, for each day in the input,
     tells you how many days you would have to wait until a warmer temperature.
    
     If there is no future day for which this is possible, put 0 instead.
    
     For example,
     given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73],
     your output should be [1, 1, 4, 2, 1, 1, 0, 0].
    
     Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
    
     */
    
    public class Daily_Temperatures {
    
        // https://leetcode.com/articles/daily-temperatures/
        class Solution {
            public int[] dailyTemperatures(int[] temperatures) {
    
                int[] result = new int[temperatures.length];
    
                if (temperatures == null || temperatures.length == 0) {
                    return result;
                }
    
                int[] next = new int[100 + 1]; // range [30,100]
                Arrays.fill(next, Integer.MAX_VALUE);
    
                for (int i = temperatures.length - 1; i >= 0; i--) {
                    int warmerIndex = Integer.MAX_VALUE;
                    for (int t = temperatures[i] + 1; t <= 100; t++) {
                        if (next[t] < warmerIndex) {
                            warmerIndex = next[t];
                        }
                    }
    
                    next[temperatures[i]] = i;
    
                    // if last day, then always 0
                    if (warmerIndex != Integer.MAX_VALUE) {
                        result[i] = warmerIndex - i;
                    }
                }
    
                return result;
            }
        }
    
        class Solution_Stack {
            public int[] dailyTemperatures(int[] temperatures) {
    
                int[] result = new int[temperatures.length];
    
                if (temperatures == null || temperatures.length == 0) {
                    return result;
                }
    
                Stack<Integer> sk = new Stack<>();
    
                for (int i = temperatures.length - 1; i >= 0; i--) {
    
                    while (!sk.isEmpty() && temperatures[i] >= temperatures[sk.peek()]) { // @note: >=
                        sk.pop();
                    }
    
                    result[i] = sk.isEmpty()? 0: sk.peek() - i;
                    sk.push(i);
                }
    
                return result;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/daily-temperatures/
    // Time: O(T)
    // Space: O(T)
    class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& A) {
            stack<int> s;
            vector<int> ans(A.size());
            for (int i = A.size() - 1; i >= 0; --i) {
                while (s.size() && A[s.top()] <= A[i]) s.pop();
                ans[i] = s.size() ? s.top() - i : 0;
                s.push(i);
            }
            return ans;
        }
    };
    
  • class Solution(object):
        def dailyTemperatures(self, temperatures):
            """
            :type temperatures: List[int]
            :rtype: List[int]
            """
            save = {}
            answer = []
            for day in range(len(temperatures) - 1, -1, -1):
                temp = temperatures[day]
                save[temp] = day
                larger = []
                for i in range(temp + 1, 102):
                    if i in save:
                        larger.append(save[i] - day)
                if larger:
                    answer.append(min(larger))
                else:
                    answer.append(0)
            return answer[::-1]
    

Java

  • class Solution {
        public int[] dailyTemperatures(int[] T) {
            int length = T.length;
            int[] waitingDays = new int[length];
            Stack<Integer> stack = new Stack<Integer>();
            Stack<Integer> indicesStack = new Stack<Integer>();
            for (int i = 0; i < length; i++) {
                int temperature = T[i];
                while (!stack.isEmpty() && stack.peek() < temperature) {
                    int prevTemperature = stack.pop();
                    int index = indicesStack.pop();
                    waitingDays[index] = i - index;
                }
                stack.push(temperature);
                indicesStack.push(i);
            }
            return waitingDays;
        }
    }
    
  • // OJ: https://leetcode.com/problems/daily-temperatures/
    // Time: O(T)
    // Space: O(T)
    class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& A) {
            stack<int> s;
            vector<int> ans(A.size());
            for (int i = A.size() - 1; i >= 0; --i) {
                while (s.size() && A[s.top()] <= A[i]) s.pop();
                ans[i] = s.size() ? s.top() - i : 0;
                s.push(i);
            }
            return ans;
        }
    };
    
  • class Solution(object):
        def dailyTemperatures(self, temperatures):
            """
            :type temperatures: List[int]
            :rtype: List[int]
            """
            save = {}
            answer = []
            for day in range(len(temperatures) - 1, -1, -1):
                temp = temperatures[day]
                save[temp] = day
                larger = []
                for i in range(temp + 1, 102):
                    if i in save:
                        larger.append(save[i] - day)
                if larger:
                    answer.append(min(larger))
                else:
                    answer.append(0)
            return answer[::-1]
    

All Problems

All Solutions