Today let’s look at LeetCode problem 239 — sliding window maxima.

Let’s start with the question:

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.

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 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 [5 3 6 6] 7 6 1 3-1 5 [3 6 7] 7

I’m going to give you an array and a k value, and in the array I’m going to have a window that starts at 0 and goes up to n minus k plus 1, and I’m going to give you the maximum value of each window.

There are many ways to solve this problem, so let’s give a general idea:

1. Violence O(n*k)

2, heap O (n * logk)

O(n)

O(n) = O(n) = O(n) = O(n)

Talk is cheap,show me the code.

Violence law

Brute force code is relatively simple, but has a fatal weakness is high complexity, direct timeout.

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

return res;
Copy the code

The heap

The heap implementation has a ready-made wrapper class in every major language, PriorityQueue in Java. The idea is to maintain a large top heap of k size, and then store subscripts instead of nums[I], because you can find nums[I] quickly with subscripts, but nums[I] can be very difficult to find subscripts, and then use index<=i-k condition, Take out the elements that exceed the window, and the last time you take the top element of the heap is the window maximum.

Initialize the first window heap, then loop through it, and then loop through all of it.

/** ** /
int n = nums.length;
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> (nums[o2] - nums[o1]));
for (int i = 0; i < k; ++i) {
    pq.offer(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[pq.peek()];
for (int i = k; i < n; ++i) {
    pq.offer(i);
    while (pq.peek() <= i - k) {
        pq.poll();
    }
    ans[i - k + 1] = nums[pq.peek()];
}
return ans;
/** ** /
if (nums.length == 0 || k == 0) {
    return new int[] {}; } PriorityQueue<Integer> pq =new PriorityQueue<>((o1, o2) -> (nums[o2] - nums[o1]));
int[] ans = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; ++i) {
    while(! pq.isEmpty() && pq.peek() <= i - k) { pq.poll(); } pq.offer(i);if (i - k + 1> =0) {
        ans[i - k + 1] = nums[pq.peek()]; }}return ans;
Copy the code

deque

Double-endided queue implementation takes advantage of the bidirectional access of the deque to ensure that the left element in the deque is always the largest, so that the largest element only needs to take deque.peekfirst () every time. Use deque.peekFirst() == i-k to ensure that elements outside the window go out. Verify the numS [I] and the size of the tail element each time you join the team. If it is larger than the tail element, remove the tail element. And then add I to the queue.

        /** * Double-ended queue * time complexity O(n+k), space complexity O(n) * always keep the first element of the double-ended queue as the maximum */
        if (nums == null || nums.length == 0) {
            return nums;
        }
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // The window is already full
            if(! deque.isEmpty() && deque.peekFirst() == i - k) {// if (! deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // Always keep the queue in order of the largest to the smallest, and always remove the newly added element smaller, if
            If nums[I] is greater than all values in the queue, all values in the queue will be removed
            while(! deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } deque.offerLast(i);// When the window is full of k elements, place them one by one in the array res[]
            if (i >= k - 1) {
                // The first element is always the largest
                res[i + 1- k] = nums[deque.peekFirst()]; }}return res;
Copy the code

Deque code actually can also be optimized, the code above is to use the system’s own Deque, my diary in front of the said system library functions tend to consider many actual industry situation and many boundary conditions, so the performance is not very good, so we can further realize a Deque, thus improve the running time.

For reference, I used the system’s own Deque, that is, the above code, running time is 39ms, beating 50.38% of Java users; My own implementation of the Deque, the code below, is running at 29ms, beating 96.29% of Java users.

/** * array implements a double-ended queue ** /
if (nums.length == 0 || k == 0) {
    return new int[] {}; }int count = k + 1;
int[] deque = new int[count];
int head = 0;
int tail = 0;
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
    if(tail ! = head && deque[head%count] == i - k) { head = (head +1) % count;
    }
    while(tail ! = head && nums[deque[(tail -1 + count) % count]] < nums[i]) {
        tail = (tail - 1 + count) % count;
    }
    deque[tail] = i;
    tail = (tail + 1) % count;
    if (i - k + 1> =0) {
        res[i - k + 1] = nums[deque[head % count]]; }}return res;
Copy the code

The Deque code for this array implementation is actually the circular double-endian queue from the previous diary. I don’t have to explain it too much. If it is not clear, you can go to the previous article on designing the circular double-endian column.

Double array

The double array method is the most efficient of all, running at 13ms, less than half the time of the array’s double-endian queue.

But how to say this method is not universal, feel a bit of cheating, orthodox method or double-endian queue elegant point.

1. Find the maximum value from the left and right, respectively. 2. Compare the maximum value of the left and right. The larger value is the maximum value of the sliding window at this position.

final int[] max_left = new int[nums.length];
final int[] max_right = new int[nums.length];

max_left[0] = nums[0];
max_right[nums.length - 1] = nums[nums.length - 1];

for (int i = 1; i < nums.length; i++) {
    max_left[i] = (i % k == 0)? nums[i] : Math.max(max_left[i -1], nums[i]);

    final int j = nums.length - i - 1;
    max_right[j] = (j % k == 0)? nums[j] : Math.max(max_right[j +1], nums[j]);
}

final int[] sliding_max = new int[nums.length - k + 1];
for (int i = 0, j = 0; i + k <= nums.length; i++) {
    sliding_max[j++] = Math.max(max_right[i], max_left[i + k - 1]);
}

return sliding_max;
Copy the code

Write in the last

Among these methods, the most efficient is the last method of the double number group, but the actual scene feels not very useful, the topic of the research point is still heap and double-endian queue. Queues are used a lot in real development scenarios. So get familiar with it.