239. Sliding Window Maximum ★

239. Sliding Window Maximum

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        left = 0
        res = []
        for right in range(len(nums)):
            if right-left+1 == k:
                res.append(max(nums[left:right+1]))
                left +=1
        return res

 

로직은 맞지만, 시간 제한에 걸림!!

 

당신 코드 👇

res.append(max(nums[left:right+1]))

이 줄이 슬라이딩 윈도우마다 O(k) 시간의 max() 연산을 하게 돼서,
총 시간복잡도는 O(n × k) 가 됩니다.
→ n이 최대 10⁵일 때 시간 초과(TLE) 발생해요.

---

✅ 해결법: deque(덱) 를 활용한 최적화 (O(n))

collections.deque를 사용해서
현재 윈도우에서 가장 큰 값의 인덱스만 관리하면
모든 연산을 O(1) 시간에 처리할 수 있어요.

---

🔧 최적화된 코드

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        q = deque() # index
        l = r= 0

        while r < len(nums):
            # 큐는 먼저 들어간데이터가 먼저 나감
            # q[0] : 제일 먼저 넣은 데이터
            # q[-1]: 제일 마지막에 넣은 데이터
            # 큐안에 데이터가 있고, 큐의 탑(직전 데이터들) 가 지금 추가할 데이터 nums[r] 보다 작으면, 앞의 데이터 삭제
            # 근데 왜 직전 데이터를 삭제하지 않고, 탑을 삭제하는지는..
            # 큐에 항상 가장 큰값이 제일 앞으로 가게 유지하기때문에, 
            # nums[q[-1]] < nums[r] 이런 상황이면, 큐에 데이터가 1개 밖에 없어서, q[0] == q[-1] 같은 상황임
            # 큐 안에 데이터 모두 삭제한다고 보면 됨            
            while q and nums[q[-1]] < nums[r]:
                q.pop() # 가장 최근 데이터(오른쪽) q[-1] 부터 삭제

            q.append(r)

            # 윈도우 크기를 벗어난, left 값은 삭제
            # left index 는 q의 제일 앞에 있을 것이므로, q[0] 을 확인하면 됨
            # 윈도우 크기 = right - left +1 이어야 하므로, 
            # 범위가 벗어나려면, 윈도우 크기 > right - left +1 상황이 되어야 함
            # while q and r-q[0]+1 < k:
            if q[0] < l: # 더 쉽게.. 계산
                q.popleft() # 가장 오래된 데이터(왼쪽) q[0] 부터 삭제

            if (r-l+1) == k:
                res.append(nums[q[0]]) # q에서 가장 왼쪽 값이, 윈도우 내에서, 가장 큰 값
                l += 1 # 윈도우 크기 유지하면서, left index 증가
            
            r+=1

        return res

 

Sliding Window Maximum 문제에서 흔히 사용하는 monotonic deque (단조 큐) 전략을 잘 구현하셨어요.
조금 더 명확하게 핵심 포인트와 코드를 정리해드릴게요.

---

✅ 핵심 개념 요약

• deque에는 인덱스만 저장하고,
• nums[q[i]]는 값 비교용으로 사용
• deque는 항상 내림차순으로 값이 정렬된 상태를 유지 (가장 큰 값이 앞에 있도록)

---

✅ 코드 리뷰 및 설명

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        q = deque()  # 값을 넣는 게 아니라 인덱스를 저장

        l = r = 0  # 윈도우의 왼쪽, 오른쪽 포인터

        while r < len(nums):
            # 1. 새로 들어오는 값보다 작은 값들은 모두 제거 (뒤에서부터)
            while q and nums[q[-1]] < nums[r]:
                q.pop()

            # 2. 현재 인덱스를 deque에 삽입
            q.append(r)

            # 3. 윈도우 범위를 벗어난 값 제거 (앞에서부터)
            if q[0] < l:
                q.popleft()

            # 4. 윈도우 크기가 k일 때만 결과 추가
            if r - l + 1 == k:
                res.append(nums[q[0]])  # 가장 앞에 있는 값이 최대값
                l += 1  # 윈도우를 오른쪽으로 한 칸 이동

            r += 1

        return res

---

✅ 예시 작동 흐름 (nums = [1,3,-1,-3,5,3,6,7], k = 3)

1. [1, 3, -1] → 큐에는 [1, 3] → max = 3
2. [3, -1, -3] → 그대로 → max = 3
3. [-1, -3, 5] → 큐의 작은 값들 제거 → [5]만 남음 → max = 5
   ...

---

✅ 아주 사소한 개선 포인트 (선택 사항)

# 이 부분은 while 말고 if 로 충분함
# while q and r - q[0] + 1 > k:
#     q.popleft()

if q[0] < l:
    q.popleft()

현재 코드에선 잘 동작하고 있고, 시간 복잡도도 O(n) 으로 효율적이에요.
따라서 지금 그대로 사용하셔도 문제 없습니다!

 

---

---

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # deque 에서 제일 왼쪽에 윈도우 내 가장 큰값 유지
        q = deque()

        l = 0
        res = []
        for r in range(len(nums)):
            # 가장 최근에 넣은 값이 현재 넣으려는 값보다 작으면, 최근에 넣은 값 삭제
            while q and nums[q[-1]] < nums[r]:
                q.pop() # q[-1] 삭제됨

            # 현재 값이 아닌, 인덱스를 추가                
            q.append(r)

            if q and q[0] < l: # q의 가장 오래된 값이 windows 범위 벗어나면, 삭제
                q.popleft()

            if r-l+1 == k:
                res.append(nums[q[0]])
                # 윈도우 크기 유지하면서 l 옮김
                l +=1

        return res