find max value(when right - left + 1 == k), do n times
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (k == 1) {
return nums;
}
int result[] = new int[nums.length - k + 1];
int left = 0;
for (int right = 0; right < nums.length; right++) {
if (right - left + 1 == k) {
int max = Integer.MIN_VALUE; // in size k window find local max
for (int i = left; i <= right; i++) {
max = Math.max(max, nums[i]);
}
result[left++] = max;
}
}
return result;
}
}
or left don't move, right move, also T: O(nk)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n-k+1];
int max = Integer.MIN_VALUE;
int i = 0;
while (i < n-k+1) {
for (int j = i; j < n; j++) {
max = Math.max(max, nums[j]);
if (j - i + 1 == k) {
res[i] = max;
max = Integer.MIN_VALUE;
i++;
break;
}
}
}
return res;
}
}
/*
naive:
int res[n-k+1]
[1 3 -1] -3 5 3 6 7
i
j
if (j-i == k)
for (int i < j) {
find max save in res, res[i] = max
i++
}
*/
Heap
之後再來寫看看
dequeue
use deque to store index,
peek() = peekFirst()
poll() = pollFirst()
offer() = offerLast()
Q. how many result?
A. (n-k+1)
0. use deque to save index, so...
check range: peek() < (i - k +1)
i-k+1就是維持 k個 sliding windows, 超出就poll(pollFront
k = 3
i 0 1 2 3, i = 3, 3-3+1 = 1, so 小於 1 的 index 都丟掉
new coming value is bigger than peekLast() (last roud latest), discard last,
(因為新的都加在尾端, 如果新來得值比last大, discard last in dq
offer new coming value index (offer: offerLast()
add result
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0) return nums;
int result[] = new int[n-k+1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n ; i++) {
if (!dq.isEmpty() && dq.peek() < (i - k + 1)) {
dq.poll();
}
while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
dq.pollLast();
}
dq.offer(i);
if ((i - k + 1) >= 0) { // i - k + 1 之後>=0 才開始有答案
result[i - k + 1] = nums[dq.peek()];
}
}
return result;
}
}
O(n)
[1, 3, - 1], 3, .....
idx = 2,
2 -3 +1 = 0, 這時候才出現第一組答案
if ((i - k + 1) >= 0) { // i - k + 1 之後>=0 才開始有答案
result[i - k + 1] = nums[dq.peek()];
}
dequeue new version
T:O(n), while loop < n, so can ignore
S: O(n), since O(n−k+1) is used for an output array and O(k) for a deque.
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<>(); //dequeue stores index
for (int i = 0; i < nums.length; i++) {
// so the queue will be a decresing mono queue,
// we abandon smaller one in queue, remain larger one in queue
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offer(i); // add data
// in here, !queue.isEmpty() 不需要, 因為已經先加資料了(queue.offer(i)
// if first index is out of windows, pop it
if (i - k + 1 > queue.peekFirst()) {
queue.pollFirst();
}
if (i - k + 1 >= 0) { // when i - k + 1 >= 0, start to collect result
res[i - k + 1] = nums[queue.peekFirst()];
}
}
return res;
}
}
/*
T:O(n), while loop < n, so can ignore
S: O(N), since O(N−k+1) is used for an output array and O(k) for a deque.
maintain a mono deque, qeueu first is always the max
[ ]
[ ]
0
[7,2,4]
1 2
i >= k-1 = 1
record index
7[0]
if (!queue.isEmpty && nums[queue.peekLast] < nums[i])
queue.pollLast
add nums[i] to queue, queue.offer(nums[i])
i - k >= quueue.peekFirst
i - k + 1 == 0
add result(nums[quueue.peekFirst])
*/
if 3 poll first, it's wrong, this max can remain for next to use,
unless , this time we poll the number is the max one, abandon it
more structure way
and offer number, not index
class Solution {
class MonoQueue {
private Deque<Integer> deque = new ArrayDeque<>();
public void offer(int num) { // remain max at last, first is max
while (!deque.isEmpty() && deque.getLast() < num) {
deque.pollLast();
}
deque.offerLast(num);
}
// why check max == poll num?
// if num we want to poll is not the max one, it doesn't matter, so
// don't poll the max
// remain max for next to see
public void poll(int num) { // out of window, poll max, first
if (deque.getFirst() == num) { // check first is num? true, poll it
deque.pollFirst();
}
}
public int getMax() { // max always in first position
return deque.getFirst();
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
MonoQueue window = new MonoQueue();
int[] result = new int[nums.length - k + 1];
int index = 0;
for (int i = 0; i < nums.length; i++) {
window.offer(nums[i]);
if (i >= k-1) { // in i = 2 (k = 3)
result[index] = window.getMax();
index++;
window.poll(nums[i - k + 1]); // in i == 2, pollfirst nums[0]
}
}
return result;
}
}
/*
0 1 k-1
[1 3 -1] -3 5 3 6 7
*/
```java
class Solution {
class MonoQueue {
Deque<Integer> deque = new ArrayDeque<>();
/*
[1 3 -1] -3 5 3 6 7
大 -> 小 mono queue
k = 3 ->
[1 3 -1] -3 5 3 6 7
x
max
Q: 3 -1 max = 3
abadon left -> 1
has abadoned
*/
public void offer(int num) {
// 注意前面有比較小的就一直排掉喔！
while (!deque.isEmpty() && num > deque.getLast()) {
deque.pollLast();
}
deque.offer(num);
}
public void poll(int num) {
if (deque.getFirst() == num) {
System.out.println("poll" + num);
deque.pollFirst();
}
}
public int getMax() {
return deque.getFirst();
}
}
/*
[1 3 -1] -3 5 3 6 7
x
大 -> 小
Ｑ
7 6 5
index 0 -> 7
find 7 in Queue -> max -> remove
if we don't remove, this max 7 will remain
because getMax -> always quque first place
7 6 5 4 3 2 1
x.
b
x
b (abandon, if this num is max one)
x
b
*/
public int[] maxSlidingWindow(int[] nums, int k) {
// how to solve find max?
// use mono queue
MonoQueue window = new MonoQueue();
int n = nums.length;
int index = 0;
int[] result = new int[n - k + 1];
for (int i = 0; i < n; i++) {
window.offer(nums[i]);
if (i - k + 1 >= 0) {
result[index++] = window.getMax();
window.poll(nums[i - k + 1]); // when idx = 2 - 3 + 1 = 0, sliding window abandon left
}
}
return result;
}
/*
T: O(n), push num, pop num -> n times
S: O(k), ksize mono queue
*/
}
```
