[Luffy]_239. Maximum sliding window value

“This is my 37th day of participating in the First Challenge 2022. For details: First Challenge 2022”

Maximum sliding window value

The title

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

Returns the maximum value in the sliding window.

Example 1

Input: nums = [1, 3, 1, 3,5,3,6,7], k = 3 output:,3,5,5,6,7 [3] : The position of the sliding window Maximum -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- [1] 3-1-3 3 5 6 7 3 1 [3-1-3] 3 5 6 7 3 1 3 [1-3-5] 3 6 7 5 3-1/3-3 5 6 7 5 1 3 1-3 [5 3 6] 7 6 1 3 1-3 5 [3 6 7] 7Copy the code

Example 2

Input: nums = [1], k = 1Copy the code

Answer key

The enumeration of violence

By enumerating the entire array O(n)O(n)O(n) O(n)O(n)O(K)O(K)O(K)O(K)O(K)O(K)O(K ∗ K)O(n* K)O(n∗ K)O(n∗ K)O(n∗ K)O(n∗ K)O(n∗ K)O(n∗ K)O(n∗ K)O(n∗ K)O(n∗ K) has a timeout risk, so it is necessary to find other ways to optimize.

Window queue

The cost of enumerating the entire array O(n)O(n)O(n) is essential. Is it possible to calculate the maximum when enumerating?

Analyze the data nums = [1, 3-1-3,5,3,6,7], k = 3 nums = [1, 3, 1-3,5,3,6,7], k = 3 nums = [1, 3-1-3,5,3,6,7], k = 3

window	An array of	The maximum
Window 1	$[1, 3, 1]$	3
Window 2	$(3, 1, 3]$	3
Window 3	$[-1, -3, 5]$	5
Window 4	$[-3, 5, 3]$	5
Window 5	$[5，3，6]$	6
Window 6	$[3，6，7]$	7

Difficulty 1: How to know the current maximum value needs to be moved out [window].

Can we do this, record the maximum index in the original array; And put the subscript in the queue StackStackStack.

− Current subscript − Current subscript − Stack [0] >= K >=k >= K; Move the beginning of the stack[0]stack[0] out of the window

Get the maximum value quickly by maintaining a StackStackStack queue during enumeration;

The difficulties in 2

If the maximum value moves out of the stackStackStack queue, how do I guarantee that stack[0]stack[0] is the maximum value of the current queue?

In this case, when maintaining a StackStackStack queue, Compare the current nums[I]nums[I]nums[I] with stack[stack.length−1]stack[stack.length-1]stack[stack.length−1]

• if
  $nums[i] >= stack[stack.length-1]$ 将
  $stack[stack.length-1]$Delete and continue to compare
  $nums[i]$ 与
  $stack[stack.length-1]$Until stack[stack.length-1] >=
  $nums[i]$; The current value
  $nums[i]$In theiIn the
  $stack$The queue
• if
  $nums[i] < stack[stack.length-1]$; To give upi
• Finally, in the [k,nums.length] range,nums [stack[0]]nums[stack[0]]nums[stack[0]] into the result array
• Return result data

Edit the code as follows:

var maxSlidingWindow = function (nums, k) {
  if (k === 1) return nums;
  const len = nums.length;
  const stack = [];
  let result = [];
  for (let i = 0; i < len; i++) {
    if (i - stack[0] >= k) stack.shift();
    while (nums[stack[stack.length - 1]] <= nums[i]) {
      stack.pop();
    }
    stack.push(i);

    if (i >= k - 1) {
      result.push(nums[stack[0]]); }}return result;
};
Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section