关于栈:算法栈

栈

先入后出

栈的利用

如果数据保留的程序和应用程序相同，那么最初保留的数据最先被应用，具备“后入先出”的特点，所以能够思考将数据保留到栈中。

后缀表达式

题目：后缀表达式是一种算术表达式，它的操作符在操作数的前面。输出一个用字符串数组示意的后缀表达式，请输入该后缀表达式的计算结果。假如输出的肯定是无效的后缀表达式。例如，后缀表达式["2"，"1"，"3"，""，"+"]对应的算术表达式是“2+13”，因而输入它的计算结果5。

/** * @param {string[]} tokens * @return {number} */var evalRPN = function(tokens) {    let stack = []    for(const token of tokens) {        switch(token) {            case "+":            case "-":            case "*":            case "/":                let num1 = stack.pop();                let num2 = stack.pop();                stack.push(calculate(num2, num1, token))                break;            default:                stack.push(Number(token))        }    }    return stack.pop()};var calculate = function(num1, num2, operator) {  switch(operator) {    case "+":      return num1 + num2;    case "-":      return num1 - num2;    case "*":      return num1 * num2;    case "/":      return num1 / num2 > 0 ? Math.floor(num1 / num2) : Math.ceil(num1 / num2);  }}

小行星碰撞

题目：输出一个示意小行星的数组，数组中每个数字的绝对值示意小行星的大小，数字的正负号示意小行星静止的方向，正号示意向右航行，负号示意向左航行。如果两颗小行星相撞，那么体积较小的小行星将会爆炸最终隐没，体积较大的小行星不受影响。如果相撞的两颗小行星大小雷同，那么它们都会爆炸隐没。航行方向雷同的小行星永远不会相撞。求最终剩下的小行星。例如，有6颗小行星[4，5，-6，4，8，-5]，如图6.2所示（箭头示意航行的方向），它们相撞之后最终剩下3颗小行星[-6，4，8]。

var asteroidCollision = function(anteroids) {  const stack = [];  for(let i = 0; i < anteroids.length; i++) {    while(stack.length && stack[stack.length-1] > 0 && stack[stack.length-1]<-anteroids[i]) {      stack.pop()    }    if(stack.length && anteroids[i] < 0 && stack[stack.length-1] == -anteroids[i]) {      stack.pop()    } else if (!stack.length || anteroids[i]>0 || stack[stack.length-1] < 0) {      stack.push(anteroids[i])    }  }  return stack;}

每日温度

题目：输出一个数组，它的每个数字是某天的温度。请计算每天须要等几天才会呈现更高的温度。例如，如果输出数组[35，31，33，36，34]，那么输入为[3，1，1，0，0]。因为第1天的温度是35℃，要等3蠢才会呈现更高的温度36℃，因而对应的输入为3。第4天的温度是36℃，前面没有更高的温度，它对应的输入是0。其余的以此类推。

暴力法

// 写错了，搞成最高温度var dailyTemperatures(temperatures) {  let result = []  for(let i = 0; i < temperatures.length; i++) {    let max = 0;    let count = 0;    for(let j = i + 1; j < temperatures.length; j++) {      if(temperatures[j]-temperatures[i]>max) {        count = j - i      }      max = Math.max(max, temperatures[j]-temperatures[i])    }    result.push(count)  }  return result;}

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

假如输出数组的长度为n。尽管上述代码中有一个嵌套的二重循环，但它的工夫复杂度是O（n），这是因为数组中每个温度入栈、出栈各1次。这种解法的空间复杂度也是O（n）。

直方图最大矩形面积

直方图是由排列在同一基线上的相邻柱子组成的图形。输出一个由非正数组成的数组，数组中的数字是直方图中柱子的高。求直方图中最大矩形面积。假如直方图中柱子的宽都为1。例如，输出数组[3，2，5，4，6，1，4，2]，其对应的直方图如图6.3所示，该直方图中最大矩形面积为12，如暗影部

枯燥栈法

矩阵中的最大矩形

请在一个由0、1组成的矩阵中找出最大的只蕴含1的矩形并输入它的面积。例如，在图6.6的矩阵中，最大的只蕴含1的矩阵如暗影局部所示，它的面积是6。

栈

栈的利用

总结