https://leetcode.com/problems/sliding-window-maximum/

---

1. 전체 코드

1-1. 시간 초과 코드

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque(nums[0:k])
        max_val = max(q)
        ans = [max_val]
        start = k
        while start < len(nums):
            x = q.popleft()
            y = nums[start]
            q.append(y)
            if x == max_val:
                max_val = max(q)
            if y > max_val:
                max_val = y
            ans.append(max_val)
            start += 1
        return ans

비록 시간 초과이지만 접근 방법은 잘 알아두자. 윈도우가 이동하면서 소멸된 왼쪽 값 x가 최대값과 같을 경우에만 max(q)를 사용한다.

x = popleft()의 값을 조건문으로 최대값인지 확인하는 방식이 마음에 들었다.

1-2. 통과 코드

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) * k == 0:
            return []
        if k == 1:
            return nums

        q = deque()
        sol = []
        for i in range(len(nums)):
            # 윈도우가 이동하면서 소멸되는 값
            if q and q[0] == i - k: 
                q.popleft()
            # 새로 들어온 값이 마지막 원소보다 크다면 마지막 원소 제거
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
            # k = 3 기준 i = 2([0,1,2]) 부터 윈도우 크기 충족
            if i >= k - 1:
                sol.append(nums[q[0]])
        return sol

첫번째 원소가 항상 최대값이 되도록 q를 구성한다.

q[0] == i - k

위 코드에서 i - k 에 해당하는 인덱스 값은 위의 while문을 통해 이전에 pop() 되어 이미 없어진 인덱스일 수 있다. q에 항상 윈도우의 모든 인덱스가 있다고 생각하면 안된다.

쉽게 생각하자면 물리적으로 윈도우가 한 칸씩 이동하면서 자연스럽게 왼쪽의 값이 하나씩 소멸되는 코드이며 이미 그전에 해당 인덱스가 사라졌을 수 있고 그건 중요하지 않다.