[leetcode 239] Sliding Window Maximum

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.

 

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]

Example 3:

Input: nums = [1,-1], k = 1 Output: [1,-1]

Example 4:

Input: nums = [9,11], k = 2 Output: [11]

Example 5:

Input: nums = [4,-2], k = 2 Output: [4]

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

문제 풀이:

문제의 핵심은 범위 안의 최댓값이 언제 바뀌는지 이다. 매번 최댓값을 업데이트하면 좋지만(brute force) 그러면 시간 복잡도가 매우 올라간다. 따라서 sliding window를 이동시켰을 때 이전 범위에서 최댓값의 인덱스처리를 잘해주는게 핵심!

 

1 priority queue사용

 

k까지는 push한 후에 top에 위치한 값을 정답에 push한다.

그 이후론 nums값을 추가한 후에 top에 위치한 인덱스가 sliding window를 벗어난다면 pop을 한다.

그리고 다시 top에 있는 값을 push

단점: 시간이 오래 걸림

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> answer;
        priority_queue<pair<int, int>> pq;
        int n = nums.size();
        
        int i=0;
        
        for(int i=0; i<k; i++){
            pq.push({nums[i], i});
        }
        answer.push_back(pq.top().first);

        for(int i=k; i<n; i++){
            pq.push({nums[i], i});
                
            while(!pq.empty() && pq.top().second < i-k+1){
                pq.pop();
            }
            
            answer.push_back(pq.top().first);   
        }
        
        return answer;
    }
};

 

 

2 deque 사용

시간을 약간 단축시킴

deque를 사용해서 priority queue를 구현한다. front에 있는 값이 현재 범위에서 가장 큰 값을 가진 인덱스이다.

dq에 값을 추가할 땐 push_back을 이용한다.

i-q.front() ==k면 최댓값이 범위를 벗어낫다는 의미이므로 pop_front()를 해준다.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> answer;
        deque<int> dq;
        int n = nums.size();
        
        for(int i=0; i<n; i++){
            while(!dq.empty() && nums[dq.back()] < nums[i]){
                dq.pop_back();
            }
            
            dq.push_back(i);
            
            if(i - dq.front() == k){
                dq.pop_front();
            }
            
            if(i>=k-1) answer.push_back(nums[dq.front()]);
        }

        return answer;
    }
};

 

 

3 배열 사용

tle 발생

마찬가지로 최댓값의 인덱스와 값을 저장한 후 최댓값의 인덱스가 벗어날때 값을 업데이트해준다.

이때 새로 추가된 값이 기존 최댓값보다 크다면 새로 추가된 값이 max이지만 그렇지 않다면 구간 내에서 다시 max를 구해줘야 한다.