Topic describes

Their thinking

Remember the solution to the 59-iI. maximum of queues? The difficulty of this problem is difficult, in fact it is not difficult to clarify the thinking, nothing more than sliding window + monotonous two-terminal queue combination. Let’s break it down step by step:

The first step

We will create a temporary sliding window array window, and then get the maximum value in the window, and finally put the maximum value in the Result array. As I keep sliding the window, I get the final result.

The second step

We only need to worry about two problems, one is how to slide the window, and the other is how to get the maximum value in the window.

(a) how to slide the window?

• If I < k-1, window.push(nums[I])

• When I = k, the last element of the window is pushed into the window, and the window is an array containing K elements. At this point, the maximum value of the window can be calculated and stored in result

• Slide the window forward, remove the last element of the window (nums[i-K-1]), add the new element to the window, and recalculate the maximum value until the array numS traversal is complete

    let result = [];
   // See below for details
    let slideWindow = new SlideWindow();
    for(let i = 0; i< nums.length; i++){
        if(i < k-1) {// Fill the window with k-1
            slideWindow.push(nums[i]);
        }else{
            // The window slides forward to move in the new element
            slideWindow.push(nums[i]);
            result.add(slideWindow.max());
            // Remove elements from the back end of the window
            slideWindow.shift(nums[i-k+1]); }}Copy the code

(2) How to obtain the maximum value of window?

Create a monotonic two-ended queue, and only put the maximum value in the queue. If the new element is smaller than the maximum value in the queue, all the new elements are removed from the queue, and the maximum value is returned. Of course, note that when the window changes, that is, when the window is enqueued, you need to determine whether the enqueued value is the maximum, and if so, you need to enqueue the maximum value and recalculate it.

 var SlideWindow = function(){
     // Hold the element of window temporarily
     this.window = [];
     // Stores the maximum value in the window
     this.queue = [];
 }
 
 SlideWindow.prototype.push = function(value){
     this.window.push(value);
     // Calculate the values stored in queue, using monotone two-ended queue, all values that do not match are queued
     while(this.queue.length && this.queue[0] < value){
         this.queue.pop();
     }
     This.queue [0] is the maximum value of the current window.
     this.queue.push(value)
 }
 
 SlideWindow.prototype.pop = function(value){
     // We need to check whether the current value is in window and queue
     if(this.window.length && value === this.window[0]) {// It exists, delete it
         this.window.shift();
     }
     if(this.queue.length && value === this.queue[0]) {this.queue.shift();
     }
 }

SlideWindow.prototype.max = function(){
    return this.queue.length ? this.queue[0] : -1;
}

Copy the code

In fact, this SlideWindow is the solution to the maximum value of the 59-iI. queue.

Ok, let’s add the two pieces of code together and that’s the final solution!

code

JS

var SlideWindow = function(){
    this.window = [];
    this.queue = [];
}

SlideWindow.prototype.push = function(val){
    while(this.queue.length && this.queue[this.queue.length - 1] < val){
        this.queue.pop();
    }
    this.window.push(val);
    this.queue.push(val);
}

SlideWindow.prototype.max = function() {
    return this.queue.length ? this.queue[0] : -1;
}

SlideWindow.prototype.pop = function(n){
    if(this.window.length && n === this.window[0]) {this.window.shift();
    }
    if(thisThe queue. length && n ===this.queue[0]) {this.queue.shift(); }}var maxSlidingWindow = function(nums, k) {
    let result = [];
    let slideWindow = new SlideWindow();
    for(let i = 0; i < nums.length; i++){
        if(i < k - 1){
            slideWindow.push(nums[i]);
        }else{
            slideWindow.push(nums[i]);
            result.push(slideWindow.max())
            slideWindow.pop(nums[i-k+1]); }}return result;
};
Copy the code

conclusion

The idea is sliding window + monotonous double – ended queue.

Time complexity: O(n)

Space complexity: O(k), the number of elements in window and queue does not exceed K.