栈

栈和队列一般不会直接在算法中出现关键字，但是从意思上要学会使用这两种数据结构

括号问题

括号匹配问题满足栈的特点

根据栈的后进先出原则，一组数据的入栈和出栈顺序刚好是对称的。比如说1、2、3、4、5、6 按顺序入栈，其对应的出栈序列就是 6、5、4、3、2、1

所以我们可以把其中一部分压进栈，把pop的结果和另一部分比较


/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const leftToRight = {
        '[':']',
        '(':')',
        '{':'}'
    }
    let array = []
    for(let i = 0;i<s.length;i++){
        if(Object.keys(leftToRight).includes(s[i])){
            array.push(leftToRight[s[i]])
        } else{
            if(!array.length || array.pop()!==s[i]){
                return false
            }
        }
    }
    return !array.length
};

递减队列

739. 每日温度

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

暴力解法

双循环你懂的


/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    let res = new Array(temperatures.length).fill(0)
    for(let i = 0 ; i<temperatures.length; i++){
        for(let j = i + 1;j<temperatures.length;j++){
            if(temperatures[j]>temperatures[i]){
                res[i] = j-i
                break
            }
        }
    }
    return res
};

使用递减栈处理

维护一个递减栈，值比之前值小的推入栈，否则推出原值，输出index值的差


/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const len = temperatures.length // 缓存数组的长度 
    const stack = [] // 初始化一个栈   
    const res = (new Array(len)).fill(0) //  初始化结果数组，注意数组定长，占位为0
    for(let i=0;i<len;i++) {
			// 拿当前值和栈最后一个值比较
      while(stack.length && temperatures[i]>temperatures[stack[stack.length-1]]){
					// 如果当前值大于栈最后一个值，出栈，并记录差值
          const index = stack.pop()
          res[index] = i-index
      }
			// 默认入栈
      stack.push(i)
    }
    // 返回结果数组
    return res 
};

最小栈

155. 最小栈

设计最小栈可以直接使用js数组的方法，最小值则暴力循环


var MinStack = function() {
    this.stack = []
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
   this.stack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if(!this.stack || !this.stack.length){
        return null
    }
    return this.stack[this.stack.length-1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    let minValue = this.stack[0]
    for(let i =0;i<this.stack.length;i++){
        if(minValue>this.stack[i]){
            minValue = this.stack[i]
        }
    }
    return minValue
};

辅助栈方法

依然是维护递减栈，每次push比较值和栈顶，小的才push，注意pop时要比较是否和栈顶值相同，一起pop


var MinStack = function() {
    this.stack = []
    this.stack2 = []
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val)
    if(this.stack2.length === 0||this.stack2[this.stack2.length-1]>=val){
        this.stack2.push(val)
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if(this.stack.pop() === this.stack2[this.stack2.length-1]){
        this.stack2.pop()
    }
};

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

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
   return  this.stack2[this.stack2.length-1]
};