LeetCode 739. Daily Temperatures

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> deque = new ArrayDeque<Integer>();
        int[] answer = new int[temperatures.length];
        deque.addFirst(0);

        for(int i=1; i<temperatures.length; i++){
            int curTemp = temperatures[i];
           
            while(!deque.isEmpty() && temperatures[deque.peekLast()]<curTemp){
            
                int index = deque.removeLast();
                answer[index]=i-index;
                
            }
            
            deque.addLast(i);
            
            if(i==temperatures.length-1 && !deque.isEmpty()){
                    while(!deque.isEmpty()){
                        int index = deque.removeLast();
                       answer[index]=0;
                    }
            }
        }
    return answer;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 현재 온도가 스택의 온도들보다 높으면
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        
        // 스택에 남은 인덱스들은 이미 answer[i] = 0 (기본값)
        return answer;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 뒤에서부터 순회
        for (int i = n - 1; i >= 0; i--) {
            // 현재 온도 이하인 날들 제거
            while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
                stack.pop();
            }
            
            // 스택이 비어있지 않으면 다음 더 따뜻한 날
            if (!stack.isEmpty()) {
                answer[i] = stack.peek() - i;
            }
            
            stack.push(i);
        }
        
        return answer;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        int[] stack = new int[n];
        int top = -1;
        
        for (int i = 0; i < n; i++) {
            while (top >= 0 && temperatures[stack[top]] < temperatures[i]) {
                int prevIndex = stack[top--];
                answer[prevIndex] = i - prevIndex;
            }
            stack[++top] = i;
        }
        
        return answer;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int today = 0; today < n; today++) {
            int currentTemp = temperatures[today];
            
            // 오늘이 더 따뜻하다면, 과거 날들의 답 계산
            while (!stack.isEmpty()) {
                int previousDay = stack.peek();
                if (temperatures[previousDay] < currentTemp) {
                    stack.pop();
                    answer[previousDay] = today - previousDay;
                } else {
                    break;
                }
            }
            
            stack.push(today);
        }
        
        return answer;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];  // 기본값 0 (더 따뜻한 날 없음)
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 현재 온도가 스택에 있는 날들보다 높으면
            // 그 날들의 답을 계산 (오늘이 답!)
            while (!stack.isEmpty() && 
                   temperatures[stack.peek()] < temperatures[i]) {
                int prevDay = stack.pop();
                answer[prevDay] = i - prevDay;
            }
            
            // 현재 날짜를 스택에 저장
            stack.push(i);
        }
        
        return answer;
    }
}

/**
 * 시간복잡도: O(n) - 각 원소는 1번 push, 최대 1번 pop
 * 공간복잡도: O(n) - 최악의 경우 모든 원소가 스택에
 * 
 * Runtime: 18-20ms (상위 80%)
 * Memory: 55MB
 */

// Next Greater Element 템플릿
public int[] nextGreaterElement(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);  // 없으면 -1
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            int idx = stack.pop();
            result[idx] = arr[i];  // 또는 i (인덱스)
        }
        stack.push(i);
    }
    
    return result;
}

// Next Smaller → 부등호만 변경
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {

// Previous Greater → 역순 순회
for (int i = n - 1; i >= 0; i--) {

// 원형 배열 → 2배 순회
for (int i = 0; i < 2 * n; i++) {
    int idx = i % n;
    // ...
}

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (temperatures[j] > temperatures[i]) {
            answer[i] = j - i;
            break;
        }
    }
}
// 시간복잡도: O(n²)