239. Sliding Window Maximum

naive

T: O(nk), sliding windows

in each k size window,

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...

1. 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 都丟掉

1. new coming value is bigger than peekLast() (last roud latest), discard last,

(因為新的都加在尾端, 如果新來得值比last大, discard last in dq

1. offer new coming value index (offer: offerLast()

2. 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
    */
}
```