239. Sliding Window Maximum

1. Description

• 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.

2. Example

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]

3. Solution

• Runtime: 179
• Time Complexity: O(N)
• 설명
  • deque를 만든다.
    • 📌deque를 사용하여 불필요한 요소들을 제거하고 유효한 최대값만 남겨 시간 복잡도를 줄인다.
    • 📌deque에 인덱스를 저장한 이유
      • window 범위 관리를 하기 위함이다.
      • nums[q[0]](윈도우에서 가장 큰 값의 인덱스를 의미)을 통해 최대값을 빠르게 가져오기 위함이다.
  • r이 len(nums)까지 도달할 때까지 반복문을 실행한다.
  • 현재 요소보다 작은 값들은 덱에서 제거한다.
    • q가 비어있지 않고 nums[q[-1]] < nums[r]일 때
    • q[-1]은 현재 덱에서 가장 최근에 추가된 인덱스이다.
    • 만약 현재 숫자(nums[r])가 덱의 마지막 숫자(nums[q[-1]])보다 크다면
      • 덱의 마지막 요소를 제거한다.
  • deque의 첫 번째 값이 윈도우 범위를 벗어나면 제거한다.
    • q[0]은 현재 덱에서 가장 큰 값을 가진 인덱스이다.
    • q[0]이 현재 윈도우 범위( l ~ r ) 밖에 없다면 제거
  • 윈도우 크기가 k이상이면 최대값 저장
    • (r + 1) >= k: 윈도우 크기 즉 r이 k에 도달했을 때, nums[q[0]]을 result에 추가한다.
    • 📌q[0]은 현재 윈도우에서 최대값의 인덱스이므로 nums[q[0]]이 최대값.
    • 📌l을 증가시키는 이유
      • l은 윈도우 크기 k가 유지된 이후에만 증가시켜야 한다.
      • r이 증가하면서 윈도우 크기를 증가시키고 k에 도달하면 l을 증가시키고 그다음 r을 증가시키는 구조이다.
  • r를 증가시켜 r이 k에 도달할 수 있도록 한다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        left = right = 0
        q = deque()
 
        while right < len(nums):
            # print("deque = ", q)
            # print("result = ", result)
            while q and nums[q[-1]] < nums[right]:
                q.pop()
            q.append(right)
 
            if left > q[0]:
                q.popleft()
            
            if (right + 1) >= k:
                result.append(nums[q[0]])
                left += 1
            right += 1
        return result

• 📌deque를 사용하는 방법에 대해서도 알게 되었다.
  • 삽입과 삭제가 모두 가능한 자료 구조이므로 최대값을 찾는데 시간 복잡도를 많이 안잡아먹을거 같다.

4. What I Learned

References

• ChatGPT
• Neetcode Solution