[알고리즘] Leetcode #239 최대 슬라이딩 윈도우 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

 

입출력 예

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

Example 2:

Input: nums = [1], k = 1 Output: [1]

Example 3:

Input: nums = [1,-1], k = 1 Output: [1,-1]

Example 4:

Input: nums = [9,11], k = 2 Output: [11]

Example 5:

Input: nums = [4,-2], k = 2 Output: [4]

 

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

 

Code

def maxSlidingWindow(self, nums, k):
    results = []
    window = collections.deque()
    current_max = float('-inf') # 시스템이 지정할 수 있는 가장 낮은 값
    for i, v in enumerate(nums):
        window.append(v)
        if i < k - 1:
            continue # 슬라이딩 윈도우 크기보다 작은 경우 pass
        
        # 새로 추가된 값이 기존 최댓값보다 큰 경우 교체
        if current_max == float('-inf'):
            current_max = max(window)
        elif v > current_max:
            current_max = v

        results.append(current_max)
        
        # 최댓값이 윈도우에서 빠지면 초기화
        if current_max == window.popleft():
            current_max = float('-inf')
    
    return results

이 문제는 파이썬의 슬라이싱 기능으로 간단하게 풀 수 있지만, 매번 max 값을 구하는 작업의 비효율을 개선하기 위해 선입선출(FIFO) 방식의 큐를 활용한다. 우선, 지정된 슬라이딩 윈도우 크기만큼 window가 차면, current_window에 window의 maximum을 할당한다. 이후, 윈도우를 한 칸씩 오른쪽으로 이동시키며 새로운 max를 계산하는 대신 이전 최댓값과 새로 들어온 값을 비교하는 작업만 거친다. 마지막으로 윈도우를 이동시킴에 따라 이전 최대값이 윈도우 밖으로 벗어나면 current_max에 float('-inf') (시스템 내 최솟값)을 할당해 다시 max를 계산하게끔 한다. 

---

 

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)