共计 2427 个字符,预计需要花费 7 分钟才能阅读完成。
栈
先入后出
栈的利用
如果数据保留的程序和应用程序相同,那么最初保留的数据最先被应用,具备“后入先出”的特点,所以能够思考将数据保留到栈中。
- 后缀表达式
题目:后缀表达式是一种算术表达式,它的操作符在操作数的前面。输出一个用字符串数组示意的后缀表达式,请输入该后缀表达式的计算结果。假如输出的肯定是无效的后缀表达式。例如,后缀表达式 [“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。