# 栈与队列

解决问题的特点

对称性栈结构可以帮我们避免重复操作避免重复操作的秘诀就是及时地将不必要的数据出栈，避免它对我们后续的遍历产生干扰。

# 典型真题快速上手-“有效括号”问题

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

输入: "()[]{}" 输出: true

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  const strObj = {
    '(': ')',
    '{': '}',
    '[': ']'
  }
  const arr = []

  for (let i = 0; i < s.length; i++) {
    const str = s[i]
    if (str === '(' || str === '[' || str === '{') {
      arr.push(strObj[str])
    } else {
      if (arr.pop() !== str) {
        return false
      }
    }
  }
  return !arr.length
}

# 单调栈

现在有一组数 [3，4，2，6，4，5，2，3] 让它们从左到右依次入栈。单调递减

const arr = [3, 4, 2, 6, 4, 5, 2, 3]
const Decrease = arr => {
  const stack = []
  for (let i = 0; i < arr.length; i++) {
    const cur = arr[i]
    while (stack.length && stack[stack.length - 1] < cur) {
      console.log(stack.pop(), '出栈')
    }
    console.log(cur, '入栈')
    stack.push(cur)
  }
}
Decrease(arr)

# 单调栈内容总结 (opens new window)

单调递增栈可以找到左起第一个比当前数字小的元素
单调递减栈可以找到左起第一个比当前数字大的元素

# 栈问题进阶-每日温度问题

739. 每日温度 (opens new window)

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

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
  const stack = []
  const res = new Array(temperatures.length).fill(0)
  for (let i = 0; i < temperatures.length; i++) {
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const top = stack.pop()
      res[top] = i - top
    }
    stack.push(i)
  }
  return res
}

# 栈的设计——“最小栈”问题

155. 最小栈 (opens new window)

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

pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

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() {
  const pop = this.stack.pop()
  if (this.stack2.length && pop === this.stack2[this.stack2.length - 1]) {
    this.stack2.pop()
  }
}

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

← 链表