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

Leetcode-cn.com/problems/sl…

Example 1:

Input: nums = [1, 3, 1, 3,5,3,6,7], k = 3 output:,3,5,5,6,7 [3] to explain: the position of the sliding window The maximum

[1 3-1] -3 5 3 6 7 3

[3-1-3] 5

[-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

Example 2:

Input: nums = [1], k = 1

Example 3:

Input: nums = [1,-1], k = 1

Example 4:

Input: nums = [9,11], k = 2 output: [11]

Example 5:

Input: nums = [4,-2], k = 2 output: [4]

Tip:

1 <= nums.length <= 105 -104 <= nums[i] <= 104 1 <= k <= nums.length

Java solution

Ideas:

  • A sliding array returns the maximum value of each scroll window as it scrolls

  • Initial idea: Maintain an array of current window sizes at the start of scrolling, record the maximum values in order, and perform a size maintenance replacement for the removed values and the moved values while scrolling

    • Size maintenance: Binary lookup updates to ordered arrays
    • Imagine updates: Build a heap of maintenance on the current window size data when the maximum is removed

  • Scenario 2: Find the maximum value of the current slide window and it will not change until you scroll beyond the current slide window (until you move to a larger value)

    • When removing the current window maximum, find the maximum again

    • Able to complete but inefficient, time out

      public static int[] maxSlidingWindow(int[] nums, int k) {
    // Move from 0
    int maxIndex = findMaxIndex(nums, 0, k);
    int length = nums.length;
    int moveStep = length - k+1;
    int[] maxNums = new int[moveStep];
    maxNums[0] = nums[maxIndex];
    for (int i = 1; i < moveStep; i++) {
        // The value moved in is I +k-1
        maxIndex = nums[maxIndex]>nums[i+k-1]? maxIndex:i+k-1;
        if (i>maxIndex) {
            maxIndex = findMaxIndex(nums,i,k+i);
        }
        maxNums[i] = nums[maxIndex];
    }

    return maxNums;
}


public static int findMaxIndex(int[] nums, int start, int end) {
    int max = start;
    for (int i = start+1; i < end; i++) {
        max = nums[i]>=nums[max]?  i:max;// Because we move to the right, we can reduce the number of steps by taking the larger value of index when everything is equal
    }
    return max;
}
Copy the code

  • See official solution: monotonic queue

    • If nums[n-1]
    • The queue is maintained according to this property
package sj.shimmer.algorithm.m4_2021;

import java.util.Deque;
import java.util.LinkedList;

import sj.shimmer.algorithm.Utils;

/** * Created by SJ on 2021/4/23. */

class D86 {
    public static void main(String[] args) {
        Utils.logArray(maxSlidingWindow(new int[] {1.3, -1, -3.5.3.6.7},3));
        Utils.logArray(maxSlidingWindow(new int[] {1},1));
        Utils.logArray(maxSlidingWindow(new int[] {1, -1},1));
        Utils.logArray(maxSlidingWindow(new int[] {9.11},2));
        Utils.logArray(maxSlidingWindow(new int[] {4, -2},2));
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            // A double-ended queue stores permanently removed data for the first K elements, strictly monotonically decreasing
            Deque<Integer> deque = new LinkedList<Integer>();
            for (int i = 0; i < k; ++i) {
                while(! deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } deque.offerLast(i); }int[] ans = new int[n - k + 1];
            ans[0] = nums[deque.peekFirst()];
            for (int i = k; i < n; ++i) {
                while(! deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } deque.offerLast(i);while (deque.peekFirst() <= i - k) {
                    deque.pollFirst();
                }
                ans[i - k + 1] = nums[deque.peekFirst()];
            }
            returnans; }}Copy the code

The official solution

Leetcode-cn.com/problems/sl…

  1. Priority queue

    The solution I envisioned here was to solve the maintenance problem with a large root heap

  2. The monotonous queue

    Reference scheme: see above

  3. Block + preprocessing

    Mathematical knowledge,