← 전체 회차
A-020● Day 202026.05.22hardleetcode #239neetcode150

슬라이딩 윈도우 최댓값

#array#queue#sliding-window#heap-priority-queue#monotonic-queue
↗ leetcode #239 · sliding-window-maximum
01

문제

· problem
P.020

슬라이딩 윈도우 최댓값

↗ leetcode #239

정수 배열 nums와 윈도우 크기 k가 주어집니다. 크기 k인 슬라이딩 윈도우가 배열의 맨 왼쪽에서 맨 오른쪽으로 이동합니다. 각 이동마다 윈도우 내의 최댓값을 구해야 합니다. 매번 윈도우가 한 칸씩 오른쪽으로 이동할 때, 각 윈도우의 최댓값들을 반환하세요.

제약
  • · 1 ≤ nums.length ≤ 10⁵
  • · -10⁴ ≤ nums[i] ≤ 10⁴
  • · 1 ≤ k ≤ nums.length
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,3,-1,-3,5,3,6,7]
3
[3,3,5,5,6,7]
example 2input → output
[1]
1
[1]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    윈도우에 정확히 k개의 원소가 있을 때부터 최댓값을 출력해야 하나요?
  • ☐
    어떤 데이터 구조를 사용하면 최댓값을 효율적으로 추적할 수 있을까요?
  • ☐
    윈도우를 벗어난 원소를 데큐에서 제거해야 하는 이유는 무엇인가요?
  • ☐
    배열 값 대신 인덱스를 데큐에 저장하는 이유는 무엇인가요?
  • ☐
    모든 원소가 같은 경우에는 어떻게 되나요?
  • ☐
    배열을 정렬한 후에 슬라이딩 윈도우를 적용할 수 있을까요?
  • ☐
    슬라이딩 윈도우 접근법이 항상 무차별 대입보다 빠를까요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 초기화: 결과 배열과 데큐 준비
○
q = collections.deque()  # index
○
q = []  # list
○
q = collections.deque()  # value
step 2· 메인 루프: 배열 순회
○
while r < len(nums):
○
while r < len(nums) - k:
○
while r < len(nums) - 1:
step 3· 데큐 유지: 더 작은 값 제거│ 중첩
○
while q and nums[q[-1]] < nums[r]:
○
while q and nums[q[-1]] <= nums[r]:
○
while q and nums[q[-1]] > nums[r]:
○
while q and nums[q[0]] < nums[r]:
step 4· 현재 원소 추가│ 중첩
○
q.append(r)
○
q.appendleft(r)
○
q.append(nums[r])
step 5· 윈도우 경계 유지: 범위 밖 원소 제거│ 중첩
○
if l > q[0]:
○
if l >= q[0]:
○
if r - l >= k:
step 6· 결과 기록: 윈도우가 완성되면 최댓값 출력│ 중첩
○
output.append(nums[q[0]])
○
output.append(nums[q[-1]])
○
output.append(q[0])
○
output.append(max(nums[l:r+1]))
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
3
        output = []
4
        q = collections.deque()  # index
5
        l = r = 0
6
        # O(n) O(n)
7
        while r < len(nums):
8
            # pop smaller values from q
9
            while q and nums[q[-1]] < nums[r]:
10
                q.pop()
11
            q.append(r)
12
13
            # remove left val from window
14
            if l > q[0]:
15
                q.popleft()
16
17
            if (r + 1) >= k:
18
                output.append(nums[q[0]])
19
                l += 1
20
            r += 1
21
22
        return output
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,3,-1,-3,5,3,6,7]
3
→
[3,3,5,5,6,7]
case 2
[1]
1
→
[1]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.