[LeetCode] 239. Sliding Window Maximum

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

정수 숫자 배열이 주어지고 배열의 맨 왼쪽에서 맨 오른쪽으로 이동하는 k 크기의 슬라이딩 윈도우가 있습니다. 슬라이딩 윈도우에서 k 개의 숫자 만 볼 수 있습니다. 슬라이딩 윈도우가 한 위치 오른쪽으로 이동할 때마다 최대 슬라이딩 윈도우를 값을 넣은 값들을 반환하세요.

✍️ 풀이

---

leetcode discuss 참고 풀이

먼저 슬라이딩 윈도우로 사용할 큐를 선언한다.
배열을 돌면서 모든 인덱스에 대해 반복을 시작한다.
1. 현재인덱스의 숫자보다 작은 숫자를 슬라이딩 윈도우에서 모두 빼낸다.
2. 현재인덱스를 슬라이딩윈도우(큐)에 삽입한다.
3. 만약, 가장 오래된 인덱스와 현재 인덱스의 차이가 k보다 크거나 같다면 오래된 인덱스를 제거한다.
마지막에 있는 i + 1 >= k는 처음 시작 시 k개 이상을 슬라이딩 윈도우 넣어보고 시작하기 위함이다.
4. 슬라이딩 윈도우에 가장 마지막 인덱스가 항상 현재 윈도우에서 가장 큰 값을 갖게 되므로 결과에 삽입한다.

🛠 코드

---

# leet code solution (Very GOOD)
from collections import deque
class Solution:
    def maxSlidingWindow(self, nums, k):
        res = []
        bigger = deque()
        for i, n in enumerate(nums):
            # make sure the rightmost one is the smallest
            while bigger and nums[bigger[-1]] <= n:
                bigger.pop()

            # add in
            bigger += [i]

            # make sure the leftmost one is in-bound
            if i - bigger[0] >= k:
                bigger.popleft()

            # if i + 1 < k, then we are initializing the bigger array
            if i + 1 >= k:
                res.append(nums[bigger[0]])
        return res

• 테스트케이스 변경으로 인한 시간초과 코드

# book solution 시간초과
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        results = []
        window = collections.deque()
        current_max = float('-inf')
        for i, v in enumerate(nums):
            window.append(v)
            if i < k - 1:
                continue

            # 새로 추가된 값이 기존 최대값보다 큰 경우 교체
            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

---

📝 정리

---

🎈 참고

---

Book 링크