leetcode 239 - Sliding Window Maximum

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

풀이 $O(n log k)$

처음 k구간을 담은 set을 만들어 놓고(중복이 가능하므로 multiset), 이후 한 칸씩 옮길 때마다 다음 값을 insert / 빠지는 값을 erase 했다. 주의할 점은 multiset에서 erase 할 때 value를 넘기면 value 값을 가지는 모든 원소를 삭제하기 때문에 iterator를 넘겨야 한다. https://www.cplusplus.com/reference/set/multiset/erase

 

iterator는 지우려고 하는 value값들 중 아무 값이나 상관없기 때문에 lower_bound로 찾아서 지웠다.

 

입력으로 들어오는 nums 배열을 순회하면서 모든 원소를 multiset에 insert 한번 $O(log k)$, lower_bound 한번 $O(log k)$, erase 한번 amortized $O(1)$ 하므로 총 시간 복잡도는 $O(n log k)$이다.

 

코드

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        multiset<int, greater<int>> ms;
        vector<int> ans;
        
        for(int i = 0; i < k; i++) {
            ms.insert(nums[i]);
        }
        ans.push_back(*ms.begin());
        
        for(int i = k; i < nums.size(); i++) {
            ms.insert(nums[i]);
            ms.erase(ms.lower_bound(nums[i-k]));

            ans.push_back(*ms.begin());
        }
        
        return ans;
    }
};

 

 

이 풀이는 multiset에 들어간 모든 원소들이 어떻게 보면 정렬을 유지하고 있는데, 사실 가장 큰 값만 구하면 되기 때문에 multiset을 사용할 필요가 없다.

 

 

풀이 $O(n)$

임의의 k 구간에서 필요한 정보는 가장 큰 값이다. 이 가장 큰 값은 구간을 한 칸 옆으로 옮길 때마다 삭제될 수도, 추가될 수도 있으니 인덱스 정보도 포함한 자료구조를 취해야 한다.

 

deque 자료구조를 사용해서 k 구간의 원소들 중 가장 큰 값을 맨 앞에 두고, 그 뒤에 나오는 원소들 중 내림차순에 해당되는 원소만 담는다. 이렇게 하면 k 구간이 옮기더라도 맨 앞 원소만 봐서 삭제될 원소인지 한 번에 알 수 있다. 또한 새로 추가되는 원소는 deque의 뒤에서부터 더 이상 필요 없는 원소를 삭제하면서 내림차순으로 유지시킬 수 있다.

 

코드

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

            dq.push_back(i);
            if (i >= k-1) {
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }
};