[leetcode] 739. Daily Temperatures

문제

 

최초 풀이 -> 2중 for문, 배열의 크기가 최대 10^5라 분명 시간 제한으로 풀리지 않을 것을 알고 있었음..

최종 풀이 -> stack을 이용해서 풀이, 스택에는 배열의 인덱스를 삽입하고 배열 for문을 돌리면서 stack에 값이 들어있거나 temperatures[스택 peek] < temperatures[배열 인덱스] 일 경우 result[스택 peek] = 배열 인덱스 - 스택 peek 으로 답을 구함.

 

최초 풀이

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int max = 0;
        int size = temperatures.length;
        int[] cnt = new int[size];

        for(int i = 0; i < size; i++) {
            for(int j = i + 1; j < size; j++) {
                if (temperatures[i] < temperatures[j]) {
                    cnt[i] = j - i;
                    break;
                }
            }
        }

        return cnt;
    }
}

 

최종 풀이

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int max = 0;
        int size = temperatures.length;
        int[] cnt = new int[size];

        Stack<Integer> st = new Stack<>();

        for(int i = 0; i < size; i++) {
            while(!st.isEmpty() && temperatures[st.peek()] < temperatures[i]) {
                cnt[st.peek()] = i - st.pop();
            }
            st.push(i);
        }

        return cnt;
    }
}