본문 바로가기
알고리즘

leetcode , Sliding Window Maximum

by kcj3054 2021. 8. 19.

문제

출처: https://leetcode.com/submissions/#/1

풀이 방법

슬라이딩 윈도우

각 칸을 [ ] 크기만큼 보면서 이동하면된다.
이때 multiset을 이용하면 가장 큰값을 알 수 있다.
빼야하는 값은 k만큼 이동하기에 num[i-k]이다

  1. 다음 원소를 볼때 먼저 k개를 유지하기 위해서 num[i-k]를 지운다.

  2. 값을 삽입

  3. 내부에서 정렬이 되어서 max값을 찾을 수 있다.

그 max를 정답 배열에 삽입..

for (int i = k; i < nums.size(); i++)
        {
             m.erase(m.find(nums[i - k]));

             m.insert(nums[i]);

             ans.push_back(*m.begin());
        }

'알고리즘' 카테고리의 다른 글

백준 6603 로또 (bfs)  (0) 2021.08.23
순열과 조합 (로또 : 6603) 백준  (0) 2021.08.23
leetcode 239. Sliding Window Maximum  (0) 2021.08.15
백준 가장 긴 증가하는 부분 수열 4 14002  (0) 2021.08.10
백준 9251 lcs  (0) 2021.08.09