# 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

```java
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)

```java
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,&#x20;

peek() = peekFirst()

poll() = pollFirst()

offer() = offerLast()

Q. how many result?&#x20;

&#x20;A. (n-k+1)

0\. use deque to save **index**, so...

1. check range:  peek() < (i - k +1)        &#x20;

&#x20;       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,&#x20;

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

1. offer new coming value index (offer: offerLast()
2. add result

```java
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,&#x20;

2 -3 +1 = 0,  這時候才出現第一組答案

```java
            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&#x20;

S: O(n), since O(n−k+1) is used for an output array and O(k) for a deque.

```java
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

## ![](/files/MspsQB7HQOLUFGB5SCdJ)

## more structure way

and offer number, not index

{% code lineNumbers="true" %}

```java
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 
*/


```

{% endcode %}

{% code lineNumbers="true" %}

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

{% endcode %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/queue/mono-queue/239.-sliding-window-maximum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.