처음에는 단순하게 maxHeap을 이용해서 O(N)만에 풀면 되지 않을까 생각했다.
윈도우를 maxHeap에 넣고 움직이면서 맨 앞의 값은 빼고, 뒤에 새로 들어오는 값은 더해주는 방식으로 구현했다.
import java.util.*;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int length = nums.length;
int answer[] = new int[length - k + 1];
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
for (int i = 0; i < k; i++) {
maxHeap.add(nums[i]);
}
answer[0] = maxHeap.peek();
for (int i = 1; i < length - k + 1; i++) {
Integer remove = nums[i - 1];
int add = nums[i + k - 1];
maxHeap.remove(remove);
maxHeap.add(add);
answer[i] = maxHeap.peek();
}
return answer;
}
}
결과는 Hard 문제 답게 TLE가 떴다...ㅠ
다시 문제 조건을 자세히 살펴봤다. 문제 조건은 아래와 같다.
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
내가 구현한 코드가 O(N)이 맞다면 nums.length<=10^5이기 때문에 시간내에 동작해야 했다.
다시 생각 해 보니 maxHeap에 넣고 빼는 동작이 logk씩 일어나기 때문에 O(NlogK)로 시간초과가 날 수 있다는 점을 생각하지 못했다.
뭔가 윈도우를 하나씩 옮기는 방법은 맞는 것 같으니, 최댓값을 구할 때 O(logK)보다 줄일 수 있는지 생각해 봤다.
일단은 문자열을 넣고 뺄때 힙구조가 아닌 Deque를 사용하는게 좋을 것 같았다. Deque는 맨앞과 맨뒤의 요소를 넣고 뺄 때 O(1)이 걸린다.
문제 풀이 방법은 아래와 같다.
1. 위의 경우와 마찬가지로 첫 k개는 Deque에 넣고 최댓값을 구한다.
2. 윈도우를 움직인다. 이 때,
- deque에는 index를 넣어두고, 현재 윈도우 안의 요소가 될 수 있는 인덱스들만 넣어 둔다.
- 새로 집어 넣는 값에 비해 작은 값들을 앞에서 부터 다 뺀다. 왜냐면 윈도우는 오른쪽으로 움직이고 있고, 현재 넣는 값보다 작은 기존의 deque에 있는 값은 영원히 최대값이 될 수 없기 때문이다.
아래는 구현한 코드이다.
import java.util.*;
class Solution {
public void moveWindow(int i, int k, ArrayDeque<Integer> deque, int[] nums) {
if (!deque.isEmpty() && deque.getFirst() == i - k) {
deque.removeFirst();
}
while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
deque.removeLast();
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
int length = nums.length;
if (length * k == 0) {
return new int[0];
}
if (k == 1) {
return nums;
}
int maxIndex = 0;
for (int i = 0; i < k; i++) {
moveWindow(i, k, deque, nums);
deque.addLast(i);
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}
int[] answer = new int[length - k + 1];
answer[0] = nums[maxIndex];
for (int i = k; i < length; i++) {
moveWindow(i, k, deque, nums);
deque.addLast(i);
answer[i - k + 1] = nums[deque.getFirst()];
}
return answer;
}
}'알고리즘 공부 > leetcode' 카테고리의 다른 글
| leetcode: Decode String (0) | 2021.02.14 |
|---|---|
| leetcode: Task Scheduler (0) | 2021.02.07 |
| leetcode: Longest Increasing Subsequence (0) | 2021.02.07 |
| leetcode: Jump Game II (0) | 2021.01.31 |
| leetcode: Longest Increasing Path in a Matrix (0) | 2021.01.31 |
