[LeetCode] Daily Temperatures

Link : https://leetcode.com/problems/daily-temperatures/description/

문제 파악

1. 현재의 온도 보다 더 높은 날짜를 구한다
2. 배열의 길이가 10^5이르모 완전 탐색을 통해 구현하면 O(n^2)이므로 timeout발생
3. O(n)으로 탐색할 수 있는 방법으로 구현

접근 방법

1. Deque<Integer> stack 생성
2. 스택에 날짜 push => 온도를 넣을경우 중복되는 온도가 있으면 날짜를 확인 할 수 없다. 또한, 날짜를 통해 온도를 확인할 수 있다.
3-1. 스택이 비어있지 않은데 이전 값(stack.peek())보다 현재 값(j)이 작으면 push => 어제보다 온도가 낮다
3-2. 스택이 비어있지 않은데 어제보다 현재 값이 크면 검사 => 어제보다 온도가 높다
			1) 어제보다 현재 값이 큰지 확인 => 크면 어제의 답을 구할 수 있다.
			   => temperatures[stack.peek()] < temperatures[j]
			2) 현재 값 - stack.pop()은 stack.pop()한 날짜보다 현재의 온도가 가장 가까운 더 높은 온도를 가진 날짜의 차이다.
			   => arr[day] = j-stack.pop()
			3) stack.pop()을 통해 이전 stack의 값과 현재의 값을 비교하는 것을 반복한다.
			   만약 stack.peek()의 값이 현재 값보다 작으면 반복을 종료한다 => 이전의 날짜보다 현재의 온도가 낮다
			4) 2.로 돌아간다.
		

 

💡 실패한 사례
1. 2 중 for 문 : 시간 초과 발생 ⇒ 2 중 for문을 통해 int[] 객체 하나 하나 stack에 넣으며 순서대로 탐색한다 ⇒ 배열의 길이가 10^5이라 시간 초과 발생

코드 구현

public int[] dailyTemperatures(int[] temperatures) {
        int []arr = new int [temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for(int j = 0; j <temperatures.length;j++) {
            while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[j]){
                int day = stack.pop();
                arr[day] = j-day;
            }
            stack.push(j);
        }
       return arr;
    }

배우게 된 점

💡 stack을 통해 탐색을 더 빠르고 효율적으로 구현할 수 있다.