[LeetCode]239. Sliding Window Maximum
Sliding Window Maximum - LeetCode
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.
- 풀이방법
- 일단 이 문제는 FIXED SIZE의 Window를 사용하는 문제이다.
- 제목 보고 내 마음대로 문제를 유추했었는데.
- 이 문제는, sliding window를 이동해 감에 따라, window의 각 위치에서 window내의 max값을 추출하는 것이다.
- 하나를 빼고, 하나를 추가하여 그 안에서 max값을 찾아야 한다.
- ?????? 하 이거 은근 어렵다 . 아니 그냥 어렵다 어떻게 하는지 모르겠다.
- num의 개수가 최대 10만개다. k도 최대 10만개다.
- Fixed size sliding window의 경우, window 크기가 k에 달하면, window를 움직임에 따라, 맨 첫 번째 수를 제거하고, 맨 뒤에 수를 하나 추가하는 식으로 진행된다.
- 아 진심 모르겠다 ㅋㅋㅋ 다 시간 초과될만한 것들로만 떠오른다....
시간초과
O(N^2) 일거 알고 이렇게 짰다. 일단 시간 초과 에러라도 봐야지 다른 사람들 풀이를 볼 생각이 들 것 같았다.
- 이건 그냥 20001개 크기의 check array를 생성하여, nums에 있는 각 element를 마주할 때 마다 check array에서 해당 element에 해당하는 index의 값을 1씩 증가시킨다. 그리고 k에 달할 경우, check에서 0보다 큰 index들을 PQ에다가 넣어서 pq에서 max를 추출한다 . 이 때 PQ에는 같은 값이 중복해서 들어가지 않게 한다.
- window를 이동시키면서, check에서 해당 값을 1 감소시킨다. 감소시킨 결과가 0이라면, PQ에서도 해당 값을 제거 시켜야 한다.
- PQ에서 remove(Object o)는 O(n)이 걸리는데 outer loop 까지 있으니 O(n^2)이 나올 수 밖에 없다 ㅋㅋ..
public static int[] maxSlidingWindow(int[] nums, int k){
int length=0;
int[] check = new int[20001];
Queue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
ArrayList < Integer > res = new ArrayList<Integer>();
int[] resArr;
if(nums.length<=k){
Arrays.sort(nums);
res.add(nums[nums.length-1]);
} else{
for(int end=0;end<nums.length;end++){
check[nums[end]+10000]++;
if(check[nums[end]+10000]>1);
else {
//System.out.println("CHECK["+nums[end]+"] : "+check[nums[end]+10000]);
q.add(nums[end]);
}
length++;
// window 사이즈가 k일 때 마다
if(length==k){
// 현재의 max값을 res에 넣는다.
//System.out.println("END : +"+ end +", QUEUE PEEK : "+q.peek());
res.add(q.peek());
// 맨 앞 element를 제거한다.
int del = nums[end-k+1];
check[del+10000]--;
if(check[del+10000]==0) {
//System.out.println("QUEUE REMOVE : "+del);
q.remove(del);
}
length--;
}
}
}
resArr = new int[res.size()];
for(int i=0;i< resArr.length;i++){
resArr[i] = res.get(i);
}
return resArr;
}Next greater element를 활용 했다는 풀이가 많이 보였다.
-
NGE가 뭔지 몰라서 NGE를 먼저 공부해봤다.
Stack말고 deque사용해야할것 같았다.
NGE 처럼, top과만 비교하다가 , top보다 큰게 나타나면 Stack안의 나머지것들과 모두 비교하고
아 이건 deque를 사용해야한다. Sliding Window 특성 상 앞에 것을 하나씩 제거해나가야하기도 하기 때문이다. (물론 NGE를 사용한다면, 무조건 제거되는 경우는 없을 수도 있다 )
-
즉 NGE 처럼 하기는 하는데 , Deque를 사용해서, 무조건 먼저 들어온애를 제거해 줄수도 있어야 한다.
-
그리고, int[] 로 return해야한다는 것.
-
기존의 max가 삭제 되었을 때, 다음 max를 찾기 위해 "Search"를 한다고 생각하면 이 문제는 시간 초과가 걸리게 된다.
- NGE 를 어떻게 했었는지 생각해 보자
- Stack에다가 첫 번째 원소를 넣어둔다.
- 그 다음 원소부터 next라고 칭한다.
- 현재 next가 stack의 top과 비교 해서, 더 작은 경우, Stack에 push한다.
- 현재 next가 stack의 top과 비교 해서, 더 큰 경우, Stack의 top을 pop한다.
- Stack의 top이 현재의 next보다 더 큰게 나올 때 까지 Stack의 element를 pop한다
- 마지막엔 현재 next를 stack에 push한다.
- NGE 를 어떻게 했었는지 생각해 보자
이 문제는 Sliding Window이기 때문에 Stack대신 Deque를 사용해야 한다. window를 이동할 때 , Stack으로 치자면 가장 아래에 쌓여있는 것을 빼내야 하기 때문이다. 하지만 Stack은 먼저 들어온 것을 빼낼 수 없다. Queue로 치자면, STack처럼 pop도 할 수 있어야 한다. 따라서 Deque를 사용해야 하는 것.
이문제는 NGE의 변형으로 볼 수 있는 것은 window를 sliding 시키면서 각 window에서의 max를 추출해 낸다는 것은, 각 원소의 우측으로 k개 내에서 가장 큰 값을 찾는 것과 같기 때문이다.
-
i >k 부터 ,
- Deque의 맨 앞에 있는 값이, 삭제하는 값과 같은지 확인 한다. —> 삭제 하는 값과 같은 경우 —> 디큐한다.
- i가 top과 비교해서 더 작거나 같은 경우, Deque에 인큐한다.
- i가 top과 비교해서 더 큰 경우, 데크의 top을 pop한다.
- i가 top과 비교해서 더 작거나 같을 때 까지 데크의 top을 pop한다.
-
i≤k 일 때 까지 :
- 현재 i가 stack의 top과 비교해서 더 작거나 같은 경우, 그냥 Deque에 enque 한다.
- 현재 i가 stack의 top과 비교해서 더 큰 경우, 데크의 top 을 pop한다.
- i가 top과 비교해서 더 작거나 같을 때 까지 데크의 top을 pop한다.
-
규칙성
22 20 19 21 19 23 이라면? , k = 6이고
22 || 20 | 19 이다가 21을 만나면 pop pop 하고 21을 push
22 || 21 이렇게 되고 그 담엔
22 || 21 ||19 이다가 23을 만나면 pop pop pop 하고 23을 push
23
—> 여기서 나오는 규칙성 : 이 Deque에서는 , top 좌측에는, top보다 작은 수가 올 수 없다. —> 즉, Deque의 First가 Deque에서 가장 큰 수에 해당된다.
public static int[] maxSlidingWindow(int[] nums, int k){
int[] res = null;
int curK=0;
// 먼저, nums의 길이 <=k의 길이인 경우
ArrayList<Integer> resList = new ArrayList<>();
if(nums.length<=k){
Arrays.sort(nums);
resList.add(nums[nums.length-1]);
}else {
Deque<int[]> dq = new LinkedList<>(); // e: {idx, nums[idx]}
for(int i=0;i<nums.length;i++){
// 현재 i가 stack의 top과 비교해서 더 큰 경우, 데크의 top 을 pop
while(dq.isEmpty()==false && dq.getLast()[1]<nums[i]) {
dq.removeLast();
}
// 현재 수도 Deque에 push한다.
dq.addLast(new int[]{i,nums[i]});
curK++;
// deque에 들어있는 수를 count한다
if(curK == k ){
// 현재 윈도우에서 max값을 저장한다.
resList.add(dq.getFirst()[1]);
// 삭제하는것이 dq의 맨 앞 것과 같은지 확인
// 만약 현재 index가 3이고, k는 1인 경우면, idx-k+1을 삭제
if(dq.getFirst()[0]==i-k+1)dq.removeFirst();
curK--;
}
}
}
res = new int[resList.size()];
for(int i=0;i<resList.size();i++)
res[i]=resList.get(i);
return res;
}위의 코드에서 속도를 높이기
위의 코드 그대로면 : JAVA제출자의 35퍼센트 보다만 빠른 속도가 나온다.
- 위의 코드에서 ArrayList가 아닌, 처음부터 int[] res에다 저장하기
- nums가 4개로 이루어져있고, k가 3이라면 window는 총 두 번이다. 측, int[] res의 길이는 2가 되어야 한다.
- 이와같이 res의 길이는 미리 알 수가 있다. nums.legnth-k+1이다.
AND
- if(nums.length<=k) 에서 바로 return하기로 바꾸기만 해도
아래와 같이 속도가 향사된다.
public static int[] maxSlidingWindow(int[] nums, int k){
int cnt=0;
int curK=0;
// 먼저, nums의 길이 <=k의 길이인 경우
int[] res = new int[nums.length-k+1];
if(nums.length<=k){
Arrays.sort(nums);
return new int[]{nums[nums.length-1]};
}else {
Deque<int[]> dq = new LinkedList<>(); // e: {idx, nums[idx]}
for(int i=0;i<nums.length;i++){
while(dq.isEmpty()==false && dq.getLast()[1]<nums[i]) {
dq.removeLast();
}
dq.addLast(new int[]{i,nums[i]});
curK++;
if(curK == k ){
res[cnt++]=dq.getFirst()[1];
// 삭제하는것이 dq의 맨 앞 것과 같은지 확인
// 만약 현재 index가 3이고, k는 1인 경우면, idx-k+1을 삭제
if(dq.getFirst()[0]==i-k+1)dq.removeFirst();
curK--;
}
}
}
return res;
}Author And Source
이 문제에 관하여([LeetCode]239. Sliding Window Maximum), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/LeetCode239.-Sliding-Window-Maximum저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
