[LeetCode] 239. Sliding Window Maximum

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

Sliding Window Maximum - LeetCode

문제 유형 : 슬라이딩 윈도우
문제 난이도 : Hard
 
문제
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.
 
정수 배열 nums를 받습니다. k의 크기를 가진 슬라이딩 윈도우가 순회할 때 각 슬라이딩 윈도우의 최대값만 담은 배열을 반환하시오.
 
풀이
덱을 이용하여 문제를 해결한다.
1. 덱에서 기한이 지난 값은 앞으로 삭제한다.
2. 새로 들어올 값보다 더 작은 값들은 뒤부터 삭제한다.
3. 새로운 값 i를 추가한다.
 
이러면 덱의 맨 앞에는 가장 큰 숫자만 남는다.
만약 i가 k-1 이상이라면 배열에 추가하고,
 
위 과정이 끝나면 배열을 반환시킨다.
 
코드
 
C++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if (n == 0 || k == 0) return {};

        vector<int> result(n - k + 1);
        deque<int> dq;

        for (int i = 0; i < n; i++) {
            while (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }

            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.front()];
            }
        }

        return result;
    }
};

 
Python3

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        
        n = len(nums)
        result = []
        dq = deque()

        for i in range(n):
            while dq and dq[0] < i-k+1:
                dq.popleft()
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()

            dq.append(i)

            if i >= k-1:
                result.append(nums[dq[0]])
        
        return result

 
Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
                dq.pollFirst();
            }
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
}