[LeetCode] 239. Sliding Window Maximum

문제 URL : https://leetcode.com/problems/sliding-window-maximum/

Sliding Window Maximum - LeetCode

 

문제접근법 : 

k사이즈 만큼 슬라이딩윈도우로 보이는 구간 영역에 가장큰값을 빠르게 찾는 문제입니다.

방법은 여러가지 입니다.

map으로도 풀수있고 ,list, deque, 로도 풀수있습니다.

두가지 방법 전부 올려드리겠습니다.

 

소스코드 : 

 

map을 이용하는 방법

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    map<int,int,greater<int>> m;
    for(int i=0;i<k;i++)
        m[nums[i]]++;
    
    vector<int> res = {m.begin()->first};
    for(int i=k;i<nums.size();i++){
        if(--m[nums[i-k]]==0)
            m.erase(nums[i-k]);
        m[nums[i]]++;
        res.push_back(m.begin()->first);
    }        
    return res;
}
};

 

 

list 이용방법 deque로도 상관없음

 

소스코드 :

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

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.