# leetcode topic

```Maximum sliding window -- leetcode 239
```

# Title Description

```Given an array of nums, there is a sliding window of size k that moves from the leftmost to the rightmost of the array. You can only see the numbers in the sliding window K. The sliding window moves only one bit to the right at a time.

Returns the maximum sliding window value.

Example:

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

Maximum position of sliding window
---------------               -----
[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
Be careful:

You can assume that k is always valid, 1 ≤ k ≤ the size of the input array, and the input array is not empty.

Can you solve this problem in linear time complexity?

Source: LeetCode
```

# thinking

``` *1. Double end queue, the maximum value is placed in the queue head
*2. If a value is larger than the value in front of it, the value in front of it will never be the maximum value.
*2. Because the current element is larger than the previous one, the maximum value of the current window is the current element, otherwise it is the maximum value of the window.
```

# Code

```package com.my.test.leetcode.array;

/**
* Title:
* Maximum sliding window -- leetcode 239
*
* Title Description:
*
Given an array of nums, there is a sliding window of size k that moves from the leftmost to the rightmost of the array. You can only see the numbers in the sliding window K. The sliding window moves only one bit to the right at a time.

Returns the maximum sliding window value.

Example:

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

Maximum position of sliding window
---------------               -----
[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
Be careful:

You can assume that k is always valid, 1 ≤ k ≤ the size of the input array, and the input array is not empty.

Can you solve this problem in linear time complexity?

Source: LeetCode
*/
public class MaxSlidingWindow
{
/**
* Train of thought:
* 1,Double ended queue, the maximum value is placed in the queue head
* 2,If a value is larger than the value in front of it, the value in front of it can never be the maximum value
* 2,Because the current element is larger than the previous one, the maximum value of the current window is the current element, otherwise it is the maximum value of the window.
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length <= 0 || k <= 0) {
return new int[0];
}
int len = nums.length;
// k is valid without checking k
int[] res = new int[len - k + 1];

// Double ended queue

for (int i=0; i<len; i++) {
// Add elements to the queue, ensure that the queue is increasing, and pop up the smaller ones
while (!cache.isEmpty() && nums[cache.peekLast()] < nums[i]) {
// Add element index to the queue
cache.removeLast();
}
// Add element index to the queue
// Expired elements in the queue need to be removed
if (i - cache.peekFirst() >= k) {
cache.removeFirst();
}
// If I > = k-1 in the queue, record the maximum value in the current queue
if (i >= k - 1) {
res[i-k+1] = nums[cache.peekFirst()];
}
}

return res;
}

public static void main(String[] args)
{
int[] nums = {1,3,1,2,0,5};
int k = 3;
System.out.println(new MaxSlidingWindow().maxSlidingWindow(nums, k));
int[] nums1 = {1,-1};
int k1 = 1;
System.out.println(new MaxSlidingWindow().maxSlidingWindow(nums1, k1));
}

}

```

Posted on Sun, 03 Nov 2019 00:28:59 -0700 by iHack