LeetCode 239. Sliding Window Maximum

📊 결과

소요시간: 다수의 시간 (매우 오래 걸림)
Runtime: 938ms (Beats 5.01%) ⚠️ 심각한 성능 문제
Memory: 62MB

💻 내 코드

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] answer = new int[nums.length-k+1];
        Deque<Integer> deque = new ArrayDeque<Integer>();
        int index=0;
        int max = -99999;
        

        for(int i=0; i<answer.length; i++){

            while(!deque.isEmpty() && deque.peekFirst()<i){
                deque.removeFirst();
            }

            if(deque.isEmpty()){
                max = -99999;
                index = 0;
                for(int j=i; j<i+k; j++){  // ⚠️ O(k) 반복
                    if(max <= nums[j]){
                        max = nums[j];
                        index=j;
                    }
                }
                answer[i]= max;
                deque.addLast(index);
            }else{
                int curr = i+k-1;
                while(!deque.isEmpty()&& nums[curr]>=nums[deque.peekFirst()]){
                    deque.removeLast();  // ⚠️ 잘못된 로직
                }
                if(!deque.isEmpty()){
                    if(deque.peekLast()==i){
                        max = nums[deque.removeLast()];
                        // deque.addLast(curr);
                    }else{
                        max = nums[deque.peekLast()];
                    }
                }else{
                    deque.addLast(curr);
                    max = nums[deque.peekLast()];
                }
                answer[i]= max;
                
                }

            }


        return answer;
    }
}

📝 평가

✔ 잘한 점

Deque 사용: 슬라이딩 윈도우에 적합한 자료구조 선택
범위 밖 제거: deque.peekFirst()<i 체크
인덱스 저장: 값이 아닌 인덱스 저장 시도
정답 배열 크기: nums.length-k+1 정확히 계산
끈기: 복잡한 문제를 끝까지 구현

✘ 심각한 문제점

O(nk) 시간복잡도:

 if(deque.isEmpty()){
     for(int j=i; j<i+k; j++){  // 매번 k개 원소 순회
         // ...
     }
 }

이 부분이 자주 실행되면 → O(nk) = 최악의 경우!
938ms의 주범

잘못된 단조 deque 로직:

 while(!deque.isEmpty()&& nums[curr]>=nums[deque.peekFirst()]){
     deque.removeLast();  // ⚠️ peekFirst와 비교하는데 removeLast?
 }

peekFirst와 비교하면서 removeLast 실행 → 논리적 오류
단조 deque 패턴이 깨짐

복잡한 분기 처리:
- if(deque.isEmpty()) vs else 분기가 너무 복잡
- 불필요한 중첩 if문
매직 넘버: -99999 → Integer.MIN_VALUE 사용해야
사용하지 않는 변수: max, index 변수가 불필요하게 복잡

✨ 최적화된 풀이

방법 1: 단조 감소 Deque (추천 ⭐⭐⭐⭐⭐)

핵심 아이디어: Deque를 단조 감소 순서로 유지

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();  // 인덱스 저장
        
        for (int i = 0; i < n; i++) {
            // 1. 윈도우 범위를 벗어난 인덱스 제거
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.removeFirst();
            }
            
            // 2. 현재 값보다 작은 값들을 뒤에서 제거 (단조 감소 유지)
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.removeLast();
            }
            
            // 3. 현재 인덱스 추가
            deque.addLast(i);
            
            // 4. 윈도우가 완성되면 최댓값 기록
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

시간복잡도: O(n) - 각 원소는 최대 1번 추가, 1번 제거 공간복잡도: O(k) Runtime: 20-25ms ✔ (약 40배 빠름!)

동작 과정 시각화

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0: nums[0]=1
  deque: [0]  (값: [1])
  
i=1: nums[1]=3
  3 > 1 → 0 제거
  deque: [1]  (값: [3])
  
i=2: nums[2]=-1
  -1 < 3 → 그냥 추가
  deque: [1, 2]  (값: [3, -1])
  i >= k-1 → result[0] = nums[1] = 3 ✓
  
i=3: nums[3]=-3
  -3 < -1 → 그냥 추가
  deque: [1, 2, 3]  (값: [3, -1, -3])
  result[1] = nums[1] = 3 ✓
  
i=4: nums[4]=5
  5 > -3 → 3 제거
  5 > -1 → 2 제거
  5 > 3 → 1 제거
  deque: [4]  (값: [5])
  result[2] = nums[4] = 5 ✓
  
i=5: nums[5]=3
  3 < 5 → 그냥 추가
  deque: [4, 5]  (값: [5, 3])
  result[3] = nums[4] = 5 ✓
  
i=6: nums[6]=6
  6 > 3 → 5 제거
  6 > 5 → 4 제거
  deque: [6]  (값: [6])
  result[4] = nums[6] = 6 ✓
  
i=7: nums[7]=7
  7 > 6 → 6 제거
  deque: [7]  (값: [7])
  result[5] = nums[7] = 7 ✓

결과: [3, 3, 5, 5, 6, 7]

방법 2: 주석 상세 버전 (학습용)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // Step 1: 윈도우 왼쪽 경계 유지
            // i - k + 1이 현재 윈도우의 시작 인덱스
            // 예: k=3, i=3일 때 윈도우는 [1, 2, 3]
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.removeFirst();
            }
            
            // Step 2: 단조 감소 유지
            // deque의 값들이 감소하도록 유지
            // 현재 값보다 작은 값들은 절대 최댓값이 될 수 없음
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.removeLast();
            }
            
            // Step 3: 현재 인덱스 추가
            deque.addLast(i);
            
            // Step 4: 결과 기록
            // 윈도우가 k개로 완성되면 (i >= k-1)
            // deque의 첫 번째 원소가 현재 윈도우의 최댓값
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

방법 3: TreeMap (이해용, 느림)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        TreeMap<Integer, Integer> map = new TreeMap<>();  // <값, 개수>
        
        // 첫 윈도우 초기화
        for (int i = 0; i < k; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        result[0] = map.lastKey();
        
        // 슬라이딩
        for (int i = k; i < n; i++) {
            // 왼쪽 원소 제거
            int left = nums[i - k];
            if (map.get(left) == 1) {
                map.remove(left);
            } else {
                map.put(left, map.get(left) - 1);
            }
            
            // 오른쪽 원소 추가
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            
            // 최댓값 기록
            result[i - k + 1] = map.lastKey();
        }
        
        return result;
    }
}

시간복잡도: O(n log k) Runtime: 80-100ms

방법 4: Priority Queue (비추천, 이해용)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]  // 값 기준 내림차순
        );
        
        for (int i = 0; i < n; i++) {
            // 현재 값 추가
            pq.offer(new int[]{nums[i], i});
            
            // 범위 밖 원소 제거
            while (!pq.isEmpty() && pq.peek()[1] < i - k + 1) {
                pq.poll();
            }
            
            // 결과 기록
            if (i >= k - 1) {
                result[i - k + 1] = pq.peek()[0];
            }
        }
        
        return result;
    }
}

시간복잡도: O(n log n) Runtime: 60-80ms

📊 성능 비교

방법	시간복잡도	공간복잡도	Runtime	Memory	가독성	추천도
원본 코드	O(nk)	O(k)	938ms	62MB	⭐	✘
단조 Deque	O(n)	O(k)	20-25ms	58MB	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐
TreeMap	O(n log k)	O(k)	80-100ms	60MB	⭐⭐⭐	⭐⭐
PriorityQueue	O(n log n)	O(n)	60-80ms	61MB	⭐⭐⭐	⭐⭐

개선 효과: 938ms → 20ms = 약 47배 빠름! 🚀

💡 핵심 인사이트

왜 원본 코드가 느린가?

문제 1: O(k) 반복

if(deque.isEmpty()){
    for(int j=i; j<i+k; j++){  // k번 반복
        // ...
    }
}

언제 deque가 비나?

윈도우가 이동할 때 최댓값이 윈도우를 벗어나면
최악의 경우: 매번 비어서 매번 O(k) 연산
총 시간: O(nk)

예시:

nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3

윈도우 [1,2,3]: deque=[2] (최댓값=3)
윈도우 [2,3,4]: 3이 범위 밖 → deque 비움 → O(k) 탐색
윈도우 [3,4,5]: 4가 범위 밖 → deque 비움 → O(k) 탐색
...
매번 O(k) → 총 O(nk)

단조 Deque의 마법

핵심 원리:

Deque를 단조 감소 순서로 유지

[큰 값] → [중간 값] → [작은 값]
   ↑
 항상 최댓값

작은 값들은 제거해도 OK!
→ 어차피 큰 값이 있으면 선택 안 됨

예시:

윈도우: [3, 1, 2]

1을 추가할 때:
- 3 > 1이므로 1은 절대 최댓값이 될 수 없음
- 하지만 일단 유지 (3이 나중에 빠질 수 있으니)
- deque: [3의 인덱스, 1의 인덱스]

2를 추가할 때:
- 2 > 1이므로 1 제거!
- 3 > 2이므로 2 유지
- deque: [3의 인덱스, 2의 인덱스]

왜 O(n)인가?

증명:

각 원소는:
1. 정확히 1번 deque에 추가
2. 최대 1번 deque에서 제거

총 연산: 2n = O(n)

직관:

“이미 처리한 원소는 다시 처리하지 않는다”

배운 점

단조 자료구조의 힘

 단조 증가/감소 유지
 → 특정 값을 O(1)에 찾기

불필요한 원소 제거

 현재 값보다 작은 값들은
 나중에도 최댓값이 될 수 없음
 → 제거해도 안전!

Amortized 분석

 worst case: O(k) 보일 수 있음
 하지만 평균: O(1)
 → 각 원소가 최대 1번 처리

인덱스 vs 값

 인덱스 저장 → 범위 체크 쉬움
 값 저장 → 범위 체크 어려움

🎯 개선 후 코드

추천: 단조 감소 Deque (최고의 성능과 가독성)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 윈도우 범위 밖 인덱스 제거
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.removeFirst();
            }
            
            // 단조 감소 유지: 현재 값보다 작은 값들 제거
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.removeLast();
            }
            
            deque.addLast(i);
            
            // 윈도우 완성 시 최댓값 기록
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

/**
 * 시간복잡도: O(n) - 각 원소 최대 1번 추가, 1번 제거
 * 공간복잡도: O(k) - deque 크기
 * 
 * Runtime: 20-25ms (상위 95%)
 * Memory: 58MB
 */

개선 효과:

✔ 938ms → 20ms (47배 빠름)
✔ O(nk) → O(n)
✔ 복잡한 분기 → 간결한 로직
✔ 불필요한 변수 제거

📚 관련 개념

알고리즘 패턴

단조 스택/큐(Monotonic Stack/Deque)
슬라이딩 윈도우(Sliding Window)
Amortized 분석

연관 개념

단조 Deque 응용
- Sliding Window Maximum (이 문제)
- Sliding Window Minimum
- Shortest Subarray with Sum >= K
실무 활용
- 시계열 분석: 이동 최댓값/최솟값
- 주식 분석: N일 최고가/최저가
- 센서 데이터: 노이즈 필터링
- 게임 개발: 시야 범위 최댓값
관련 문제 패턴
- Next Greater Element
- Largest Rectangle in Histogram
- Trapping Rain Water

🎓 다음 단계

비슷한 문제

LeetCode 1438. Longest Continuous Subarray With Absolute Diff <= Limit ⭐⭐⭐
- 단조 deque 2개 사용
LeetCode 862. Shortest Subarray with Sum at Least K ⭐⭐⭐⭐⭐
- 단조 deque + Prefix Sum
LeetCode 1696. Jump Game VI ⭐⭐⭐
- DP + 단조 deque
LeetCode 739. Daily Temperatures ⭐⭐
- 단조 스택 기초
LeetCode 84. Largest Rectangle in Histogram ⭐⭐⭐⭐⭐
- 단조 스택 고급

연습 포인트 체크리스트

단조 Deque 패턴 암기
손으로 시뮬레이션 3번
k=2, 3, 4로 다양한 케이스 테스트
Daily Temperatures(#739) 복습
Shortest Subarray(#862) 도전
O(n) 증명 작성

🔍 단조 Deque 마스터하기

패턴 템플릿

// 단조 감소 Deque (최댓값 찾기)
Deque<Integer> deque = new ArrayDeque<>();

for (int i = 0; i < n; i++) {
    // 1. 범위 밖 제거
    while (!deque.isEmpty() && deque.peekFirst() < 범위_시작) {
        deque.removeFirst();
    }
    
    // 2. 단조성 유지 (현재보다 작은 값 제거)
    while (!deque.isEmpty() && arr[deque.peekLast()] < arr[i]) {
        deque.removeLast();
    }
    
    // 3. 현재 추가
    deque.addLast(i);
    
    // 4. 최댓값 = deque.peekFirst()
}

최솟값 찾기로 변경

// 단조 증가 Deque (최솟값 찾기)
// 부등호만 반대로!
while (!deque.isEmpty() && arr[deque.peekLast()] > arr[i]) {
    deque.removeLast();
}

🏷️ Keywords

#MonotonicDeque #SlidingWindow #MaxSlidingWindow #Deque #단조큐 #슬라이딩윈도우
#AmortizedO(n) #WindowMaximum #IndexTracking #DequePattern #LeetCodeHard
#최적화 #Hard난이도 #코딩테스트 #자료구조응용