This is the 10th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Hello everyone, I am a senior programmer ~

Today to share a Tencent interview question, if you like, remember to pay attention to yo ~

Problem description

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:

Input: [2,3,4,2,6,2,5,1], 3

Output: [4,4,6,6,6,5]

To analyze problems

The key to this problem is to find the maximum value in a sliding window. For a sliding window of size K, we can work out its maximum value by traversing, which requires O(k) time complexity. For the array NUMs of size N, there are n-k+1 Windows, so the time complexity of this algorithm is O(nk).

Through observation, we can know that for two adjacent sliding Windows, k-1 elements are shared and only one element is changed, so we can use this property to optimize our algorithm.

For the maximum problem, we can use the priority queue (big push) to solve. First, we put the first K elements of the array into the priority queue. Whenever we move to the right window, we can put a new element in the queue, the pile top element is the maximum number of all elements in the heap, but the maximum possible does not belong to the current sliding window, we need to remove the element for processing (if the maximum value is not in the current sliding window, it can only be left to the left side of the border of the sliding window, So when the slider moves to the right, the element no longer appears in the slider, so we can remove it. We keep removing the top element of the heap until it actually appears in the sliding window. At this point, the heap top element is the maximum in the sliding window.

In order to conveniently judge the position relationship between the top element of the heap and the sliding window, we can store the binary group (num, index) in the priority queue, indicating that the subscript of element NUM in the array is index.

Little was catnip: Since python only provides a small top heap, we need to invert the elements. For example, for the list [1, -3], we invert the elements and insert them into the small top heap, which looks like [-1,3]. We take the top element -1 and invert it to 1 to get the maximum value of the list 1.

Let’s take nums=[2,3,4,2,6,2,5,1] and k=3 as examples to see the specific process.

  1. First of all, we put the first 3 elements of NUMS into the priority queue. The index value of the first element in the queue is 2>0, so it is added into the result. At this time, res=[4].

  2. The next element 2 joins the queue, and the index of the first element of the queue is 2>1, which is in the window, so it is added to the result. At this time, res=[4,4].

  3. The next element 6 joins the queue, and the index of the first element in the queue is 4>2, so it is added to the result. At this time, res=[4,4,6].

  4. The next element 2 is added to the queue, and the index of the first element in the queue is 4>3, so it is added to the result, and then res=[4,4,6,6].

  5. The next element 5 joins the queue, and the index of the first element is in the window, so it is added to the result, and res=[4,4,6,6,6].

  6. The next element in queue 1, index=4<5, is not in the window, so we pop it, index= 6, is in the window, so we add it to the result, now res=[4,4,6,6,6,5].

The advanced

We can also solve this problem using a double-endian queue. In the process of traversing the number group, we continuously perform the operation of joining the queue to the corresponding subscripts of the elements. In the process of entering and leaving the queue, we need to ensure that the elements corresponding to the subscripts stored in the queue are sorted from large to small. Specifically, when there is a new element whose index is larger than the element at the end of the queue, we need to eject the end of the queue and repeat until the queue is empty or the new element is smaller than the element at the end of the queue.

Since the subscript elements in the queue are strictly monotonically decreasing, the element corresponding to the first subscript of the queue is the maximum in the sliding window. But the maximum may be to the left of the left edge of the sliding window, and as the window moves to the right, it will never appear in the sliding window. So we also need to keep popping elements from the head of the queue until the head of the queue element is in the window.

Let’s take nums=[2,3,4,2,6,2,5,1] and k=3. We first initialize an empty queue QUE.

  1. At this point, the queue is que empty, and the subscript 0 corresponding to element 2 enters the queue. In this case, no window is formed.

  2. At this point, queue que=[0], the element at the end of the queue is 0, which corresponds to the element in the array nums[0] < NUMs [1], so we pop 0 at the end of the queue, and the queue is empty, and we add 1 to the queue. In this case, no window is formed.

  3. At this point, the queue que=[1], the element at the end of the queue is 1, and the element in the corresponding array is nums[1] < NUMs [2]. Therefore, we pop out the end 1 of the queue, and the queue is empty, and we add 2 to the queue. And now the first element 1 is in the window [0,2], so fetch the first element.

  4. At this point, queue que=[2], the element at the end of the queue is 2, and the element in its corresponding array is nums[2] > NUMs [3], so we add 3 to the queue. And now the first element 1 is in the window [1,3], so take out the first element.

  5. At this point, queue que=[2,3], the element at the end of queue 3, the element in the array corresponding to it is nums[3] < NUMs [4], so we pop the end of queue 3, and the element in the array corresponding to the element at the end of queue is nums[2] < NUMs [4], so we pop the end of queue 2, and the queue is empty. We will join the team four times. And now the first element 4 is in the window [2,4], so take out the first element.

  6. At this point, queue que=[4], the element at the end of the queue is 4, and the element in its corresponding array is nums[4] > NUMs [5], so we add 5 to the queue. And now the first element 4 is in the window [3,5], so we take out the first element.

  7. At this point, the queue que=[4, 5], the element at the end of the queue is 5, and the element in the array corresponding to it is nums[5] < NUMs [6], so we pop the element at the end of the queue 5, and the element in the array corresponding to the element at the end of the queue is NUMs [4] > NUMs [6], so we add 6 to the queue. And now the first element 4 is in the window [4, 6], so we take out the first element.

  8. At this point, queue que=[4,6], the element at the end of the queue is 6, and the element in the corresponding array is nums[6] > nums[7], so we add 7 to the queue. At this time, the first element 4 is not in the window [5,7], so we remove it from the queue, and the first element 6 is in the window [5,7], so we remove it.

Let’s take a look at the code implementation.

import collections class Solution: def maxSlidingWindow(self, nums, k): Q = collections.deque() # initialize first window for I in range(k): While q and nums[I] >= nums[q[-1]]: Q.op () # add the first element to the result ans = [nums[q[0]]] # move the window gradually to the right for I in range(k, n): While q and nums[I] >= nums[q[-1]]: Q.op () # Until the queue is empty, or smaller than the last element, q.ppend (I) # If the first element of the queue is not in the window, exit operation while q[0] <= i-k: Ans. Append (nums[q[0]]) return ans s=Solution() print(s.maaxslidingwindow ([2,3,4,2,6,2,5,1],3)Copy the code

The last

Originality is not easy! If you think the article is good, you may as well like (reading), leave a message, forward three consecutive go!

The more you know, the more you open your mind. I’ll see you next time.