[LeetCode] 239. Sliding Window Maximum

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

Algorithm

누구나 첫 접근은 쉽지만, 시간 초과 해결이 관건인 문제이다... ㅎ

monotonically Decreasing queue 개념을 이용하면 O(n)의 시간 복잡도로 풀 수 있다!

queue q를 만들고,여기에 nums 원소 인덱스를 하나씩 추가해 나가며 monotonic q를 만든다.

이때, 값을 넣기전 현재값이 덱 끝값보다 크다면 덱에서 제거한다. (ex_ q = [1,2,3,4] 현재값=7 ~> 4,3,2,1 순으로 pop()하고 7을 넣는다.)

윈도우 크기가 k일대부터 결과에 최댓값을 추가하고, 슬라이딩 윈도우를 이동한다.

수도코드. 시간복잡도는 O(n)이 된다.

---

Python

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        output = []
        q = deque()
        l = r = 0

        while r < len(nums):
            # 현재 값보다 작은 값들을 데크에서 제거
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r) # 현재 인덱스 추가

            # 윈도우 범위를 벗어난 경우,데크에서 해당 인덱스 제거
            if l > q[0]:
                q.popleft()

            # 윈도우크기가 k일때부터 결과에 최댓값 추가
            if (r + 1) >= k:
                output.append(nums[q[0]])
                l += 1
            r += 1
        
        return output

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];  // 결과 배열 초기화
        int j = 0;  // 결과 배열의 인덱스
        Deque<Integer> q = new LinkedList<>();  // 데크를 사용하여 인덱스를 저장

        for (int i = 0; i < nums.length; i++) {
            // 현재 값보다 작은 값들을 데크에서 제거
            while (!q.isEmpty() && nums[i] > nums[q.peekLast()])
                q.pollLast();

            // 현재 인덱스를 데크에 추가
            q.offer(i);

            // 윈도우 범위를 벗어난 경우, 데크에서 가장 왼쪽의 인덱스를 제거
            if (!q.isEmpty() && q.peekFirst() < j)
                q.pollFirst();

            // 윈도우 크기가 k일 때부터 결과에 최댓값을 추가
            if (i+1 >= k)
                ans[j++] = nums[q.peekFirst()];
        }
        return ans;
    }
}