【js】-【栈、队-应用】-学习笔记

声明：本笔记是根据掘金小册总结的，如果要学习更多细节，请移步https://juejin.cn/book/6844733800300150797

1 括号匹配问题-栈

描述：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。

输入: “([)]”
输出: false

输入: “{[]}”
输出: true

function isValid( s ) {
    
    #1 用一个 map 来维护左括号和右括号的对应关系
    var map=new Map()
    map.set("(",")")
    map.set("{","}")
    map.set("[","]")
    #2 无串为true
    if (!s)  return true;·
	#3 初始化 stack 数组
    var stack=[]

    for(let i=0;i<s.length;i++){
    
    	# 3.1 若是左括号，对应右括号入栈
        if(map.has(s[i]))
            stack.push(map.get(s[i]))
        else{
    
        # 3.2 若栈不为空，且栈顶的左括号没有和当前字符匹配
            if(!stack.length||stack.pop()!==s[i])  return false
        }
    }
    if(stack.length!==0) return false
    return true
}

2 每日温度问题-栈

描述:
根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替

思路：维持一个递减栈
当遍历过的温度，维持的是一个单调递减的态势时，j将温度的索引下标执行入栈操作；
只要出现了一个数字，它打破了这种单调递减的趋势，也就是说它比前一个温度值高，这时我们就对前后两个温度的索引下标求差，得出前一个温度距离第一次升温的目标差值
1.初始化递减栈stack，结果数组res，默认都是0
2.当前温度比栈顶温度大的时候，就计算下标的差值，差值放入结果res，并出栈（循环）
3.如果比栈顶小，索引继续入栈
4.最后返回结果数组res

我感觉这题也是空间换时间，时间复杂度就是O(n)

// 入参是温度数组
const dailyTemperatures = function(T) {
    
    const len = T.length // 缓存数组的长度 
    const stack = [] // 初始化一个栈 
    
    const res = (new Array(len)).fill(0) // 初始化结果数组，注意数组定长，占位为0
    for(let i=0;i<len;i++) {
    
      // 若栈不为0，且存在打破递减趋势的温度值
      while(stack.length && T[i] > T[stack[stack.length-1]]) {
    
        // 将栈顶温度值对应的索引出栈
        const top = stack.pop()  
        // 计算 当前栈顶温度值与第一个高于它的温度值 的索引差值
        res[top] = i - top 
      }
      // 注意栈里存的不是温度值，而是索引值，这是为了后面方便计算
      stack.push(i)
    }
    // 返回结果数组
    return res 
};

3 最小栈问题-栈

描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

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

定义辅助栈stack2

1. 入栈：小于等于辅助栈顶元素，则进入stack2
2. 出栈：：判断是不是和栈顶元素相等，如果是的话，stack2 也要出栈
3. 取栈顶：常规方法，数组最后一项。
4. 取最小值：由于整个栈从栈底到栈顶递减，因此stack2栈顶元素就是最小元素。

const MinStack = function() {
    
    this.stack = [];
    #1 定义辅助栈
    this.stack2 = [];
};


MinStack.prototype.push = function(x) {
    
    this.stack.push(x);
    #2.1 若入栈的值小于当前最小值，则推入辅助栈栈顶
    if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
    
        this.stack2.push(x);
    }
};


MinStack.prototype.pop = function() {
    
    #2.2 若出栈的值和当前最小值相等，那么辅助栈也要对栈顶元素进行出栈，确保最小值的有效性
    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 辅助栈的栈顶，存的就是目标中的最小值
    return this.stack2[this.stack2.length-1];
};

4 用栈实现一个队列-两个栈

描述：使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例：

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); # 返回 1，不出队
queue.pop(); # 返回 1，出队
queue.empty(); # 返回 false

1.入队： 入stack1；
2.pop出队：从stack2出栈，若stack2空，则把stack1的出栈到stack2，再从stack2中出栈（相当于把stack1的东西给逆序）
3.peek返回队首：和pop一样，只是不需要出栈，只是返回即可
3.empty操作：两个栈都为空，即队列空

代码:

const MyQueue = function () {
    
  #1 初始化两个栈
  this.stack1 = [];
  this.stack2 = [];
};

MyQueue.prototype.push = function (x) {
    
  // 直接调度数组的 push 方法
  this.stack1.push(x);
};

MyQueue.prototype.pop = function () {
    
  #1 假如 stack2 为空，需要将 stack1 的元素转移进来
  if (this.stack2.length <= 0) {
    

    while (this.stack1.length !== 0) {
    
      #2 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  #3 从 stack2 里出栈元素
  return this.stack2.pop();
};


MyQueue.prototype.peek = function () {
    
  #1 假如 stack2 为空，需要将 stack1 的元素转移进来
  if (this.stack2.length <= 0) {
     
    while (this.stack1.length != 0) {
    
      #2 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  #3 若stack2非空，返回栈顶元素
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};


MyQueue.prototype.empty = function () {
    
  # 若 stack1 和 stack2 均为空，那么队列空
  return !this.stack1.length && !this.stack2.length;
};

5 双端队列

双端队列就是允许在队列的两端进行插入和删除的队列

示例：

const queue = [1,2,3,4] # 定义一个双端队列   
queue.push(1) # 双端队列尾部入队 
queue.pop() # 双端队列尾部出队   
queue.shift() # 双端队列头部出队 
queue.unshift(1) # 双端队列头部入队

6 滑动窗口问题

描述：
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,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
1 3 -1 -3 5 [3 6 7]

最大值：3 3 5 5 6 7

方法1.双指针+遍历

1. 定义左右指针，分别在第0位，和第k-1位
2. 在每次前进过程都计算当前区间里最小的，记录结果数组
3. 返回结果res

时间复杂度：
然后每个窗口内部我们又会固定执行 k 次遍历。因此这个时间复杂度简化后用大 O 表示法可以记为 O(kn)。

const maxSlidingWindow = function (nums, k) {
    
 
  const len = nums.length;
  #1 定义结果数组
  const res = [];
  
  #2 初始化左、右指针
  let left = 0, right = k - 1;
  
  // 当数组没有被遍历完时，执行循环体内的逻辑
  while (right < len) {
    
    #3 计算当前窗口内的最大值
    const max = calMax(nums, left, right);
    
    #3.1 将最大值推入结果数组
    res.push(max);
    
    #3.2 左指针、右指针前进一步
    left++;
    right++;
  }
  // 返回结果数组
  return res;
};

// 这个函数用来计算最大值
function calMax(arr, left, right) {
    
  // 处理数组为空的边界情况
  if (!arr || !arr.length) {
    
    return;
  }
  // 初始化 maxNum 的值为窗口内第一个元素
  let maxNum = arr[left];
  // 遍历窗口内所有元素，更新 maxNum 的值
  for (let i = left; i <= right; i++) {
    
    if (arr[i] > maxNum) {
    
      maxNum = arr[i];
    }
  }
  // 返回最大值
  return maxNum;
}

这种方法直接用Math.max()更清晰

const maxSlidingWindow = function (nums, k) {
    
  const len = nums.length;
  #1 定义结果数组
  const res = [];
  
  #2 初始化左、右指针
  let left = 0, right = k - 1;

  while (right < len) {
    
  
    #3 计算当前窗口内的最大值
    let max=nums[left];
    for(let i=left;i<=right;i++){
    
    	max=Math.max(max,nums[i]);
    }
    
    #3.1 将最大值推入结果数组
    res.push(max);
    
    #3.2 左指针、右指针前进一步
    left++;
    right++;
  }
  // 返回结果数组
  return res;
};

方法2：双端队列法（牛皮的方法）

在窗口发生移动时，只根据发生变化的元素对最大值进行更新

有效的递减队列

1. 定义一个双端的队列
2. 当前的nums[i]大于队尾的，那就把队尾较小的都出队
3. 当队头的元素超过滑动窗口的最左侧，那么出队
4. 当当遍历的个数大于k的时候开始更新结果res数组

const maxSlidingWindow = function (nums, k) {
    
  
  const len = nums.length;
  // 初始化结果数组
  const res = [];
  #1 初始化双端队列
  const deque = [];
  
  // 开始遍历数组
  for (let i = 0; i < len; i++) {
    
   #2 当队尾元素小于当前元素时,将队尾元素（索引）不断出队，直至队尾元素大于等于当前元素
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
    
      deque.pop();
    }
    // 入队当前元素索引（注意是索引）
    deque.push(i);
    
    #3 当队头元素的索引已经被排除在滑动窗口之外时,队头元素索引出队
    while (deque.length && deque[0] <= i - k) {
    
      deque.shift();
    }
    #4 判断滑动窗口的状态，只有在被遍历的元素个数大于 k 的时候，才更新结果数组
    if (i >= k - 1) {
    
      res.push(nums[deque[0]]);
    }
  }
  // 返回结果数组
  return res;
};