Daily Temperatures

XXX. Daily Temperatures

Stack

Array

Monotonic Stack

Problem Statement:

Given an array of daily temperatures, return an array that tells you how many days you would have to wait until a warmer temperature. If there is no future warmer temperature, return 0 instead.

• Return array should have same length as input
• Each value represents days until warmer temperature
• Return 0 if no warmer temperature exists

Algorithm:

1. **Monotonic Stack Approach**:
   • Use stack to track indices of temperatures
   • Maintain decreasing temperatures in stack
   • Pop when finding warmer temperature
2. **Process Flow**:
   • Compare current temperature with stack top
   • Pop and calculate days difference when warmer
   • Push current index to stack

Complexity:

Time Complexity: O(n), each element is pushed and popped at most once
Space Complexity: O(n) for the stack

Implementation:

Java Solution:

public int[] dailyTemperatures(int[] temps) {
    Stack stack = new Stack<>();          // Stack stores indices
    int[] ret = new int[temps.length];            // Store days until warmer
    
    for (int i = 0; i < temps.length; i++) {
        while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
            int idx = stack.pop();                 // Pop colder temperature
            ret[idx] = i - idx;                    // Calculate days difference
        }
        stack.push(i);                            // Push current index
    }
    return ret;
}
                

Python Solution:

def dailyTemperatures(self, temps: List[int]) -> List[int]:
    stack = []                                    # Stack stores indices
    ret = [0] * len(temps)                        # Initialize result array
    
    for i in range(len(temps)):
        while stack and temps[i] > temps[stack[-1]]:
            idx = stack.pop()                     # Pop colder temperature
            ret[idx] = i - idx                    # Calculate days difference
        stack.append(i)                          # Push current index
    
    return ret
                

C++ Solution:

vector dailyTemperatures(vector& temps) {
    stack stack;                            // Stack stores indices
    vector ret(temps.size());               // Initialize result array
    
    for (int i = 0; i < temps.size(); i++) {
        while (!stack.empty() && temps[i] > temps[stack.top()]) {
            int idx = stack.top();               // Pop colder temperature
            stack.pop();
            ret[idx] = i - idx;                  // Calculate days difference
        }
        stack.push(i);                          // Push current index
    }
    return ret;
}
                

Explanation:

• **Stack Properties**:
  • Maintains indices in decreasing temperature order
  • Top of stack is most recent unresolved temperature
  • Empty stack means no unresolved temperatures
• **Processing Steps**:
  • Compare current with stack top temperature
  • Pop all colder temperatures and update their wait days
  • Always push current index for future comparison
• **Result Building**:
  • Default value 0 for temperatures with no warmer day
  • Calculate days difference when finding warmer temperature
  • Stack may still contain elements after processing (no warmer day found)