【算法】栈【算法】栈

栈先入后出
栈的应用
如果数据保存的顺序和使用顺序相反，那么最后保存的数据最先被使用，具有“后入先出”的特点，所以可以考虑将数据保存到栈中。

后缀表达式

题目：后缀表达式是一种算术表达式，它的操作符在操作数的后面。输入一个用字符串数组表示的后缀表达式，请输出该后缀表达式的计算结果。假设输入的一定是有效的后缀表达式。例如，后缀表达式["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）。