[JS] - [stack, team - application] - learning notes

Statement ： This note is based on the Nuggets brochure , If you want to learn more details , Please move https://juejin.cn/book/6844733800300150797

1 Bracket matching problem - Stack

describe ：
Given one only includes ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ String , Determines whether the string is valid .

Input : “([)]”
Output : false

Input : “{[]}”
Output : true

function isValid( s ) {
    
    #1  Use one  map  To maintain the correspondence between the left bracket and the right bracket 
    var map=new Map()
    map.set("(",")")
    map.set("{","}")
    map.set("[","]")
    #2  No string is true
    if (!s)  return true;·
	#3  initialization  stack  Array 
    var stack=[]

    for(let i=0;i<s.length;i++){
    
    	# 3.1  If it's left bracket , Corresponding right bracket stack 
        if(map.has(s[i]))
            stack.push(map.get(s[i]))
        else{
    
        # 3.2  If the stack is not empty , And the left bracket at the top of the stack does not match the current character 
            if(!stack.length||stack.pop()!==s[i])  return false
        }
    }
    if(stack.length!==0) return false
    return true
}

2 Daily temperature problem - Stack

describe :
According to the daily temperature list , Please regenerate a list , The output of the corresponding position is how long it needs to wait before the temperature rises beyond the number of days of the day . If it doesn't go up , Please use... In this position 0 Instead of

Ideas ： Maintain a decrement stack
When the traversed temperature , When maintaining a monotonous decreasing trend ,j Stack the index subscript of the temperature ;
As long as a number appears , It breaks this monotonous decreasing trend , That is to say, it is higher than the previous temperature value high , At this time, we calculate the difference between the index subscripts of the two temperatures , Get the target difference between the previous temperature and the first temperature rise
1. Initialize decrement stack stack, Result array res, The default is 0
2. When the current temperature is higher than the stack top temperature , Just calculate the difference between the subscripts , The difference is put into the result res, And out of the stack （ loop ）
3. If it's smaller than the top of the stack , The index continues to stack
4. Last returned result array res

I think this question is space for time , Time complexity is O(n)

//  The input parameter is the temperature array 
const dailyTemperatures = function(T) {
    
    const len = T.length //  The length of the cache array  
    const stack = [] //  Initialize a stack  
    
    const res = (new Array(len)).fill(0) //  Initializing the result array , Note the fixed length of the array , Space occupying 0
    for(let i=0;i<len;i++) {
    
      //  If the stack is not 0, And there is a temperature value that breaks the decreasing trend 
      while(stack.length && T[i] > T[stack[stack.length-1]]) {
    
        //  Index the stack top temperature value out of the stack 
        const top = stack.pop()  
        //  Calculation   The current stack top temperature value is the same as the first temperature value higher than it   Index difference of 
        res[top] = i - top 
      }
      //  Note that the temperature value is not stored in the stack , It's the index value , This is for the convenience of later calculation 
      stack.push(i)
    }
    //  Return result array 
    return res 
};

3 Minimum stack problem - Stack

describe ：
Design a support push ,pop ,top operation , And can retrieve the stack of the smallest elements in a constant time

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); -->  return  -3.
minStack.pop();
minStack.top(); -->  return  0.
minStack.getMin(); -->  return  -2.

Define auxiliary stack stack2

1. Push ： Less than or equal to the auxiliary stack top element , entering stack2
2. Out of the stack ：： Determine whether it is related to the top element of the stack equal , If so ,stack2 Also out of the stack
3. Take the top ： Conventional methods , Last item in array .
4. Minimum value ： Because the whole stack decreases from the bottom to the top , therefore stack2 To the top of the stack Element is the smallest element .

const MinStack = function() {
    
    this.stack = [];
    #1  Define auxiliary stack 
    this.stack2 = [];
};


MinStack.prototype.push = function(x) {
    
    this.stack.push(x);
    #2.1  If the stack value is less than the current minimum value , Push to the top of the auxiliary stack 
    if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
    
        this.stack2.push(x);
    }
};


MinStack.prototype.pop = function() {
    
    #2.2  If the value out of the stack is equal to the current minimum value , The auxiliary stack also needs to stack the top elements , Ensure the validity of the minimum value 
    if(this.stack.pop() == this.stack2[this.stack2.length-1]){
    
        this.stack2.pop();
    }
};


MinStack.prototype.top = function() {
    
    return this.stack[this.stack.length-1];
};


MinStack.prototype.getMin = function() {
    
    #3  The top of the auxiliary stack , What is stored is the minimum value in the target 
    return this.stack2[this.stack2.length-1];
};

4 Implement a queue with stack - Two stacks

describe ： Use the stack to implement the following operations of the queue ：

push(x) – Put an element at the end of the queue .
pop() – Remove elements from the head of the queue .
peek() – Return the elements of the queue header .
empty() – Whether the return queue is empty .

Example ：

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); #  return  1, Not out of the team 
queue.pop(); #  return  1, Out of the team 
queue.empty(); #  return  false

1. The team ： Enter into stack1;
2.pop Out of the team ： from stack2 Out of the stack , if stack2 empty , Then put stack1 Out of the stack to stack2, Again from stack2 In the stack （ Is equivalent to stack1 Things are in reverse order ）
3.peek Back to the head of the team ： and pop equally , It just doesn't need to be out of the stack , Just return
3.empty operation ： Both stacks are empty , That is, the queue is empty

Code :

const MyQueue = function () {
    
  #1  Initialize two stacks 
  this.stack1 = [];
  this.stack2 = [];
};

MyQueue.prototype.push = function (x) {
    
  //  Direct scheduling of arrays  push  Method 
  this.stack1.push(x);
};

MyQueue.prototype.pop = function () {
    
  #1  If  stack2  It's empty , Need to put  stack1  The elements of are transferred in 
  if (this.stack2.length <= 0) {
    

    while (this.stack1.length !== 0) {
    
      #2  take  stack1  Push the elements out of the stack  stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  #3  from  stack2  Out of the stack elements 
  return this.stack2.pop();
};


MyQueue.prototype.peek = function () {
    
  #1  If  stack2  It's empty , Need to put  stack1  The elements of are transferred in 
  if (this.stack2.length <= 0) {
     
    while (this.stack1.length != 0) {
    
      #2  take  stack1  Push the elements out of the stack  stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  #3  if stack2 Non empty , Back to top of stack element 
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};


MyQueue.prototype.empty = function () {
    
  #  if  stack1  and  stack2  All empty. , Then the queue is empty 
  return !this.stack1.length && !this.stack2.length;
};

5 deque

A double ended queue is a queue that allows insertion and deletion at both ends of the queue

Example ：

const queue = [1,2,3,4] #  Define a double ended queue    
queue.push(1) #  The tail of the double ended queue enters the queue  
queue.pop() #  The end of the double ended queue goes out    
queue.shift() #  The head of the double ended queue goes out  
queue.unshift(1) #  The head of the double ended queue enters the queue 

6 Sliding window problem

describe ：
Given an array nums And the size of the sliding window k, Please find the maximum value in all sliding windows

Input : nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output : [3,3,5,5,6,7]

The process ：

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

 Maximum ：3 3 5 5 6 7

Method 1. Double pointer + Traverse

1. Define left and right pointers , In the first 0 position , And the k-1 position
2. Calculate the minimum in the current interval in each forward process , Record result array
3. Return results res

Time complexity ：
Then inside each window, we will perform fixed execution k Time to traverse the . Therefore, this time complexity is simplified and then used to increase O The notation can be written as O(kn).

const maxSlidingWindow = function (nums, k) {
    
 
  const len = nums.length;
  #1  Define result array 
  const res = [];
  
  #2  Initialize left 、 Right pointer 
  let left = 0, right = k - 1;
  
  //  When the array is not traversed , Execute the logic in the loop body 
  while (right < len) {
    
    #3  Calculate the maximum value in the current window 
    const max = calMax(nums, left, right);
    
    #3.1  Push the maximum value into the result array 
    res.push(max);
    
    #3.2  Left pointer 、 The right pointer advances one step 
    left++;
    right++;
  }
  //  Return result array 
  return res;
};

//  This function is used to calculate the maximum value 
function calMax(arr, left, right) {
    
  //  Handle the boundary case when the array is empty 
  if (!arr || !arr.length) {
    
    return;
  }
  //  initialization  maxNum  The value of is the first element in the window 
  let maxNum = arr[left];
  //  Traverse all elements in the window , to update  maxNum  Value 
  for (let i = left; i <= right; i++) {
    
    if (arr[i] > maxNum) {
    
      maxNum = arr[i];
    }
  }
  //  Return maximum 
  return maxNum;
}

This method directly uses Math.max() Clearer

const maxSlidingWindow = function (nums, k) {
    
  const len = nums.length;
  #1  Define result array 
  const res = [];
  
  #2  Initialize left 、 Right pointer 
  let left = 0, right = k - 1;

  while (right < len) {
    
  
    #3  Calculate the maximum value in the current window 
    let max=nums[left];
    for(let i=left;i<=right;i++){
    
    	max=Math.max(max,nums[i]);
    }
    
    #3.1  Push the maximum value into the result array 
    res.push(max);
    
    #3.2  Left pointer 、 The right pointer advances one step 
    left++;
    right++;
  }
  //  Return result array 
  return res;
};

Method 2： Two terminal queue method （ The method of cowhide ）

When the window moves , The maximum value is updated only according to the changed element

Valid decrement queue

1. Define a double ended queue
2. Current nums[i] Larger than the tail of the team , Then get the smaller ones out of the team
3. When the element of the team head exceeds the leftmost side of the sliding window , Then get out of the team
4. When the number of traversals is greater than k Start updating results when res Array

const maxSlidingWindow = function (nums, k) {
    
  
  const len = nums.length;
  //  Initializing the result array 
  const res = [];
  #1  Initialize the two terminal queue 
  const deque = [];
  
  //  Start traversing array 
  for (let i = 0; i < len; i++) {
    
   #2  When the tail element is smaller than the current element , Put the end of the line element （ Indexes ） Keep getting out of the team , Until the end of the queue element is greater than or equal to the current element 
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
    
      deque.pop();
    }
    //  Index of the current element queued （ Note the index ）
    deque.push(i);
    
    #3  When the index of the queue header element has been excluded from the sliding window , The queue header element indexes out of the queue 
    while (deque.length && deque[0] <= i - k) {
    
      deque.shift();
    }
    #4  Determine the status of the sliding window , Only when the number of elements traversed is greater than  k  When , To update the result array 
    if (i >= k - 1) {
    
      res.push(nums[deque[0]]);
    }
  }
  //  Return result array 
  return res;
};