栈算法题

栈结构，先进后出

• 最小栈

  
  
  function MinStack(){
    this.stack = []
    this.min = [Infinity]
  }
  
  MinStack.prototype.push = function(item){
    this.stack.push(item)
    this.min.push(Math.min(this.min[this.min.length-1],item))
  }
  
  MinStack.prototype.pop = function{
    this.stack.pop()
    this.min.pop()
  }
  
  MinStack.prototype.top = function{
    return this.stack[this.stack.length-1]
  }
  
  MinStack.prototype.min = function{
    return this.min[this.min.length-1]
  }
  

• 判断括号是否合法

// ()
// []
// {}
// ({[)]}
function bracketCheck(str){
  const brackets = {
    '(':')',
    '{':'}',
    '[':']'
  }
  let stack = []
  for(let i = 0 ;i<str.length;i++){
    if(brackets[str[i]]){
      stack.push([str[i]])
    }else if(str[i] !== brackets[stack.pop()]){
      // 这个写法6⃣️啊
      return false
    }
  }
  return stack.length === 0
}

• 生成n对括号
  数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

function generateParenthesis(n){
  //n对括号
  //可用的左括号数量l=n
  //可用的右括号数量r=n
  const res = []
  DFS(n,n,'')
  return res

  function DFS(l,r,str){
    // 考虑合理闭合的括号组合
    // 生成过程中左右括号可使用的数量
    if(str.length===2*n){
      // 2n个字符说明凑够一种
      return res.push(str)
    }
    if(l>0){
      // 左括号有就能用
      DFS(l-1,r,str+'(')
    }
    if(l<r){
      DFS(l,r-1,str+')')
    }
  }
}

• 删除字符串内相邻重复项
  给出由小写字母组成的字符串 S ，删除所有相邻重复项

  // 'ababccca'
  // pre = ''
  // c = a
  // stack = ['',a]
  
  // pre = a
  // c = c
  // stack = ['',a,c]
  
  // pre = c
  // c = c
  // stack = ['',a]
  
  // pre = a
  // c = c
  // stack = ['',a,c]
  
  //
  function delDup(s){
    const stack = [s[0]]
    for(let i = 1 ;i < s.length ;i++){
      const pre = stack.pop()
      // 每次取出上一个末尾字符
      const cur = s[i]
      if(cur !== pre){
        // 不是相同字符则存储起来
        // 是相同字符则由于pop方法已经从结果中删除
        stack.push(pre,cur)
      }
    }
    return stack.join('')
  }
  

• 滑动窗口最大值

  // k 为窗口大小
  // window存储数组索引
  function maxInSlideWin(arr,k){
    let res = []
    let window = []
    // window存储索引
    for(let i = 0 ; i < arr.length ; i++){
      if(i-window[0]>=k){
        // 窗口大小超过限制
        window.shift()
        // 抛弃前面的值
      }
      while(arr[window[window.length-1]]<=arr[i]){
        // 用指针位置的值与窗口尾部索引值比较
        // 循环删除比指针小的值索引
        window.pop()
      }
      window.push(i)
      // i之前都比i大
      if(i>=k-1){
        // 索引k-1开始收集窗口最大值，
        // k-1之前窗口都还没到尺寸
        res.push(arr[window[0]])
        // 保证窗口内最左值=边索引为最大值
      }
    }
    return res
  }