# 239.Sliding-Window-Maximum

## 239. Sliding Window Maximum

## 题目地址

<https://leetcode.com/problems/sliding-window-maximum/>

## 题目描述

```
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?
```

## 代码

### Approach 1: Use a hammer (TLE)

**Complexity Analysis**

* Time complexity : `O(Nk)`, where `N` is number of elements in the array.
* Space complexity : `O(N-k+1)` for an output array.

```java
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
      int n = nums.length;
      if (n * k == 0) return new int[0];

      int[] output = new int[n - k + 1];
      for (int i = 0; i < n - k + 1； i++) {
        int max = Integer.MIN_VALUE;
        for (int j = i; j < i + k; j++) {
          max = Math.max(max, nums[j]);
        }
        output[i] = max;
      }

      return output;
  }
}
```

### Approach 2: Deque

Deque 每次将最大的元素的index放在首位

```java
class Solution {
    ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
    int[] nums;
    public int[] maxSlidingWindow(int[] nums, int k) {
      int n = nums.length;
      if (n * k == 0) return new int[0];
      if (k == 1) return nums;

      this.nums = nums;
      int max_idx = 0;
      for (int i = 0; i < k; i++) {
          cleanDeque(i, k);
          deq.addLast(i);
          if (nums[i] > nums[max_idx]) {
              max_idx = i;
          }
      }

      int[] output = new int[n - k + 1];
      output[0] = nums[max_idx];

      for (int i = k; i < n; i++) {
          cleanDeque(i, k);
          deq.addLast(i);
          output[i - k + 1] = nums[deq.getFirst()];
      }

      return output;
    }

  public void cleanDeque(int i, int k) {
    // remove indexes of elements not from sliding window
    if (!deq.isEmpty() && deq.getFirst() == i - k) {
        deq.removeFirst();
    }
    // remove from deq indexes of all elements
    // which are smaller than current elemnt num[i]
    while (!deq.isEmpty() && nums[i] > nums[deq.getLast()]) {
        deq.removeLast();
    }
  }
}
```

### Approach #3 Dynamic programming

`[i % k == 0, ~ i]` 中左边block的最大值赋值给 `left[i]`, 边界右

`[i, i % k == 0]` 中右边block的最大值赋值给 `right[i]`，边界左

**Complexity Analysis**

* Time complexity : O(*N*), since all we do is `3` passes along the array of length N.
* Space complexity : O(*N*) to keep `left` and `right` arrays of length `N`, and output array of length `N - k + 1`.

```java
class Solution {
  public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n * k == 0)    return new int[0];
    if (k == 1) return nums;

    int[] left = new int[n];
    left[0] = nums[0];
    int[] right = new int[n];
    right[n - 1] = nums[n - 1];
    for (int i = 1; i < n; i++) {
      if (i % k == 0) { 
        left[i] = nums[i];
      } else {
        left[i] = Math.max(left[i - 1], nums[i]);
      }

      int j = n - i - 1;
      if ((j + 1) % k == 0) {
        right[j] = nums[j];
      } else {
        right[j] = Math.max(right[j + 1], nums[j]);
      }

      int[] output = new int[n - k + 1];
      for (int i = 0; i < n - k + 1; i++) {
        output[i] = Math.max(left[i + k - 1], right[i]);
      }

      return output;
  }
}
```


---

# 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://wentao-shao.gitbook.io/leetcode/array/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.