# Sliding Window Maximum

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

**Example**

For array`[1, 2, 7, 7, 8]`, moving window size`k = 3`. return`[7, 7, 8]`

At first the window is at the start of the array like this

`[|1, 2, 7| ,7, 8]`, return the maximum`7`;

then the window move one step forward.

`[1, |2, 7 ,7|, 8]`, return the maximum`7`;

then the window move one step forward again.

`[1, 2, |7, 7, 8|]`, return the maximum`8`;

分析

Deque双端队列, deque就是linkedlist ,deque 两头都可进可出 ,deque里元素单调递减

Deque offer，add加入末尾，push加入头

O(N\*K),每个元素都push 和pop一次 2n，所以是O(N)

用Deque双端队列来解。分为添加元素和删除元素两部步。

1. 初始化第一个窗口（0-第k－1个元素），一次向deque中加入数组中的元素。每次加入新元素时，若deque中最后一个元素比新元素小，则删去，直到deque中最后一个元素比新元素大时停止（或deque为空时停止），然后加入新元素。
2. 添加元素：从第k的元素开始，每次加入新元素时，若deque中最后一个元素比新元素小，则删去，直到deque中最后一个元素比新元素大时停止（或deque为空时停止），然后加入新元素。此时deque中第一个元素即为当前窗口的最大值，加入答案中。
3. 删除元素：应该删去（当前位置－k）位置的元素，看deque第一个元素是否和要删除元素相等，若不相等则说明在之前的元素加入过程中该元素已经删去，则不用做任何操作，否则删去deque中第一个元素即可。

```
public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: The maximum number inside the window at each moving.
     */
    private void inQueue(Deque<Integer> q, int num){
        while(!q.isEmpty() && q.peekLast() < num){
            q.pollLast();
        }
        q.offer(num);
    }

    private void outQueue(Deque<Integer> q, int num){
        if(num == q.peekFirst()){
            q.pollFirst();
        }
    }

    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        int n = nums.length;

       Deque<Integer> q = new ArrayDeque<Integer>();
       ArrayList<Integer> ret = new ArrayList<Integer>();
       if(n == 0)
           return ret;
       //只到k-1因为k开始需要取结果了，之前不需要取只需要加数字
        for(int i = 0; i < k-1; i ++){
           inQueue(q, nums[i]);
        }
        for(int i = k-1; i < n; i ++){
            inQueue(q, nums[i]);
            ret.add(q.peekFirst());
            outQueue(q, nums[i-k+1]);
        }
        return ret;
    }
}
```

python

入列：维持递减队列（每个数进入dp，把比他小的都弹出），最大的总在队首，每次队首加入res

出列：队首和nums\[i-k+1]比较，==就弹出，不是的话证明dp size不够K，不必弹

```
双端队列(Deque),可以维持一个递增的双端队列
EX:[|1, 4|, 5, 3, 9], k = 3
我们先将k-1个元素放入队列:|2|
然后从第k个元素开始，一次加入新元素并删除旧元素，并且保持滑动窗口的size不变
[|1, 4, 5|, 3, 9], Deque: 5, Output: [5];
[1, |4, 5, 3|, 9], Deque: 5, 5, Output: [5, 5];
[1, 4, |5, 3, 9|], Deque: 8, Output: [5, 5, 8];
因为对于每个数组中的元素只扫描一次，所以总体时间在deque操作中也近似于线性，所以总运行时间：O(n)(amortized), 空间复杂度:O(1)
```

```
class Solution:

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        dq = collections.deque()
        for i in range(k-1):
            self.inQueue(dq, nums[i])#初始只到k-1,不到k，并且这里也要pop q if necessary
        l = len(nums)
        res = []
        for i in range(k-1, l):
            self.inQueue(dq, nums[i])
            res.append(dq[0])
            self.outQueue(dq, nums[i-k+1])
        return res


    def inQueue(self, dq:collections.deque, k: int):
        while dq and dq[-1]  < k:
            dq.pop()
        dq.append(k)

    def outQueue(self, dq:collections.deque, k: int):
        if dq[0] == k:
            dq.popleft()
```


---

# 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://nataliekung.gitbook.io/ladder_code/qiang-hua-4-shuang-zhi-zhen-ff09/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.