栈算法题
技巧1：栈内存放 数据数组下标，比较时通过 数据数组下标拿到数据进行比较
存放 数据数组下标，可以快速定位数据位置(直接拿到下标)，也可以通过下标快速拿数据
但是 存放数据的话就不好再去拿下标，
用于 需要操作下标的情况
技巧2：需要位置对比的题目，队列 或 栈 内放的不是数，而是位置i
技巧3：递增栈，递减栈，前n项最大/最小值栈
3.有效的括号（ LeetCode 20 ）
注意 存在 循环结束以后 stack不为空的情况（如‘[{(’），须return false
var isValid = function(s) {
let array = s.split('')
const map = {
')':'(',
'}':'{',
']':'[',
}
const left = ['{','[','(']
let stack = []
for(let i = 0; i < array.length; i++) {
if(left.includes(array[i])) {
stack.push(array[i])
} else {
const temp = stack.pop()
if(temp !== map[array[i]]) return false
}
}
return !stack.length
};4.基本计算器（ LeetCode 224 ）
操作符有 + - ( )，四个
leetcode
都是+-法，无需考虑括号的优先执行顺序，而是考虑 用+-反号的性质解括号。
利用stack记录 每层括号的 + -，将括号内的数字直接与括号的+-相乘，从而直接解括号
var calculate = function(s) {
let ops = [1] // 用来记住每一层括号的正负号
let currentSign = 1
let res = 0
const l = s.length
for(let i = 0; i < l; i++) {
if(s[i] === ' ') {
} else if(s[i] === '+') {
currentSign = +ops[ops.length - 1]
} else if(s[i] === '-') {
currentSign = -ops[ops.length - 1]
} else if(s[i] === '(') { // 遇见括号就把 括号内数字解括号后 的正负记录下来
ops.push(currentSign) // 内层还有括号的话,跳出后还用
} else if(s[i] === ')') { // 括号只起反转正负的作用,未按括号的顺序去计算
ops.pop()
} else { // 数字,发现了数字就往后找一串数字
let number = ''
while(i < l && !isNaN(s[i]) && s[i] !== ' ') {
number = number + s[i]
i++
}
res = res + currentSign * number
i--
}
}
return res
};自己的解法
未考虑数字大于10的
括号内用了递归
var calculate = function(s) {
let temp = s.replace(/\s+/g,"").split('')
return compute(temp)
};
var compute = function(temp) {
let stack = []
for(let i = 0; i < temp.length; i++) {
if(temp[i] === '(') { // 如果是左括号，就拿到左括号和右括号间的内容，递归
let temp1 = []
let btacketCount = 1
for(i = i + 1;i < temp.length; i ++) { // 直接用i计算，从'('下一位开始
if(temp[i] === ')') btacketCount-- // 碰见')' 就减1
if(temp[i] === '(') btacketCount++
if(btacketCount === 0) break
temp1.push(temp[i])
}
const result = compute(temp1)
if(stack.length) {
const operator = stack.pop() // 拿到栈顶运算符
if(operator === '+') {
stack[stack.length - 1] = +stack[stack.length - 1] + +result
} else if(operator === '-') {
stack[stack.length - 1] = +stack[stack.length - 1] - +result
}
} else {
stack.push(+result)
}
continue; // 开始计算下一个,此时i指向')'
}
if(temp[i] === '+'|| temp[i] === '-') { // 如果是计算符号，直接push
stack.push(temp[i])
continue;
}
if(!isNaN(temp[i]) && stack.length) { // 如果是数字,并且栈顶有元素(此元素必然是符号+-)
const operator = stack.pop() // 拿到栈顶运算符
if(operator === '+') {
stack[stack.length - 1] = +stack[stack.length - 1] + +temp[i]
} else if(operator === '-') {
stack[stack.length - 1] = +stack[stack.length - 1] - +temp[i]
}
} else {
stack.push(temp[i])
}
}
return stack.pop()
}5.最小栈（ LeetCode 155 ）
注意这里给的是TS,同时注意,标答能保证时间复杂度为O(1)
class MinStack {
protected Stack:number[] = [];
protected MinStack:number[] = [];
// 每次给Stack放数,都会给MinStack放一次前n个最小的数
// MinStack每个数都是对应Stack位置的前N个数中最小的数.
push(val: number): void {
this.Stack.push(val);
this.MinStack.push(Math.min(val, this.getMin() ?? Number.POSITIVE_INFINITY ));
}
pop(): void {
this.Stack.pop();
this.MinStack.pop();
}
top(): number {
return this.Stack[this.Stack.length - 1];
}
getMin(): number {
return this.MinStack[this.MinStack.length - 1];
}
}自己的解法
写题时暴露的问题:
min 忘了赋初始值,且应为this.stack[0]
忘了写this,stack拼写错误
时间复杂度为O(n)
var MinStack = function() {
this.stack = []
};
MinStack.prototype.push = function(val) {
this.stack.push(val)
};
MinStack.prototype.pop = function() {
return this.stack.pop()
};
MinStack.prototype.top = function() {
return this.stack.length ? this.stack[this.stack.length -1] : null
};
MinStack.prototype.getMin = function() {
let min = this.stack[0] ? this.stack[0] : null
for(let i=0;i<this.stack.length;i++) {
if(this.stack[i] < min) min = this.stack[i]
}
return min
};6.验证栈序列（ LeetCode 946 ）
每次push完之后，查看poped内有没有相同的数，有就pop，并且popIndex + 1
var validateStackSequences = function (pushed, popped) {
const stack = []
let popIndex = 0
for (let i = 0; i < pushed.length; i++) {
stack.push(pushed[i])
while (stack.length && stack[stack.length - 1] === popped[popIndex]) {
stack.pop()
popIndex++
}
}
return stack.length === 0
}7.每日温度（ LeetCode 739 ）
var dailyTemperatures = function(temperatures) {
let stack = [] // 记录 温度下标
let result = new Array(temperatures.length).fill(0)
for(let i = 0; i < temperatures.length; i++) { // 遍历每一天的温度
while(stack.length && temperatures[i] > temperatures[stack[stack.length -1]]) {
// 当天温度 依次比较栈内温度
// 如果 比栈内元素温度高，代表栈内元素找到了比自己温度更高的天数
// (栈内永远保持了,越栈底温度越高,即单调递增)
// 从栈顶向栈底依次比较，将比自己小的弹出,并记录index插值,即result值,放入result对应下标
const popDay = stack.pop()
result[popDay] = i - popDay
}
// 注意:此时，当前下标之下，存放的是 前几天，也是比自己更高温 的下标,或者无下标
stack.push(i)
}
return result
};自己的解法
最后循环赋值0的方式，没有直接开头全部标0的好。
var dailyTemperatures = function (temperatures) {
const stack = []
const res = []
for (let i = 0; i < temperatures.length; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const index = stack.pop()
res[index] = i - index
}
stack.push(i)
}
for (let i = 0; i < stack.length; i++) {
res[stack[i]] = 0
}
return res
};8.接雨水（ LeetCode 42 ）
把比自己小的从栈内顶出去，计算完水之后，再将自己push进去。
决定水高度的并不是当前pop的index，而是当前pop的index左侧的left
注意，水的height为，const currHeight = Math.min(height[left], height[i]) - height[top];
注意 left 不一定存在，要判断stack还有没有数。
注意 宽为 i - left, 当前pop的index仅用于height计算中减去的底。
// 单调栈
var trap = function (height) {
const s = []
let res = 0
for (let i = 0; i < height.length; i++) {
while (s.length && height[i] > height[s[s.length - 1]]) {
const index = s.pop()
if (!s.length) break
const left = s[s.length - 1]
const currentHeight = Math.min(height[i], height[left]) - height[index]
res = res + currentHeight * (i - left - 1)
}
s.push(i)
}
return res
};
//双指针
var trap = function(height) {
let ans = 0;
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
};带注释版
var trap = function(height) {
const stack = []; // 由于需要操作下标,所以栈内储存下标,比较时需要数据直接通过下标拿
let ans = 0; // 结果
const n = height.length;
// 一个个与凹槽内进行对比,弹出比自己低的柱子(stack.length>2且存在比自己低的柱子会产生凹槽),并计算水量
for (let i = 0; i < n; ++i) {
while (stack.length && height[i] > height[stack[stack.length - 1]]) {
// 把凹槽top拿出来计算存水量,并pop删除,此处凹槽相当于填上了,后续将以left为top
const top = stack.pop();
if (!stack.length) { // 弹出一个,栈内就没了,那就存不了水,必须得有left(栈内left必>top)
break;
}
const left = stack[stack.length - 1]; // 拿到top左边的下标,栈内top左边必比top高
const currWidth = i - left - 1; // 宽度就是 top右 - top左 下标相减 再-1
// 水高度就是木桶效应,拿短的一边再减去,中间top的高度
// 如果此时left = top,即连续两个等高的柱子在栈内,则水高为0,符合逻辑
const currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
// 比自己小的凹槽top弹完后,push自己,成为top
stack.push(i);
}
return ans;
};9.逆波兰表达式求值（ LeetCode 42 ）
输入：tokens = [“2”,”1”,”+”,”3”,”*”]
输出：9
leetcode
注意:
放入时转换为number
要求除法向零截断，小于0 要ceil，大于0 要floor
var evalRPN = function (tokens) { const stack = [] for (let i = 0; i < tokens.length; i++) { const item = tokens[i] if (!isNaN(item)) { stack.push(Number(item)) continue; } const right = stack.pop() const left = stack.pop() if (item === '+') { stack.push(left + right) } else if (item === '-') { stack.push(left - right) } else if (item === '*') { stack.push(left * right) } else if (item === '/') { stack.push(left / right > 0 ? Math.floor(left / right) : Math.ceil(left / right)) } } return stack[0] }
10.柱状图中最大的矩形（ LeetCode 84 ）
构建一个单调递增栈，对于每一根柱子来说，其能组成的最大矩形，就是两侧低于自己高度的柱子，夹住的部分的面积
该面积为 自己的高度 * 左右边界的index差值
而单调递增栈，左侧必然比自己小，就是自己的左边界，只要再找到右侧比自己小的，即是右边界
因而每一个柱子都可以弹出栈内比自己高的柱子，因为该柱子即是比自己高的柱子的右边界。
var largestRectangleArea = function (heights) {
const s = []
const h = [0, ...heights, 0]
let max = 0
for (let i = 0; i < h.length; i++) {
while (s.length && h[s[s.length - 1]] > h[i]) {
const cur = s.pop()
max = Math.max(max, h[cur] * (i - s[s.length - 1] - 1))
}
s.push(i)
}
return max
};11.最大矩形（ LeetCode 85 ）
充满0或1的二维数组的矩形中找出由1拼成的最大矩形
largestRectangleArea就是 84题，将二维数组转化为多个矩形问题利用84题解法解决。
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
每一row构建一个heights，也就是柱状图，调用largestRectangleArea得到最大面积，
循环到matrix[0]、matrix[1]、matrix[2]、matrix[3]时各自计算其柱状图数据(heights)，
每row的heights的每个height，由当前row 和 上一行的 旧heights决定。
如果当前row为0，则height为0；如果当前row为1，则height为 旧height + 1
注意: 1.初始heights须全为0， 2.matrix中所有数都是字符串格式
就像将当前row及其上部的row看成柱状图，以当前row为底
下部连续的1累加视为高度，直到出现0(0之上的1不能继续累加，不视为高度)
var maximalRectangle = function(matrix) {
const heights = new Array(matrix[0].length).fill(0)
let max = 0
for(let row = 0; row < matrix.length; row++) {
for(let col = 0; col < matrix[0].length; col++) {
heights[col] = matrix[row][col] === '1' ? Number(heights[col]) + 1 : 0
}
max = Math.max(max, largestRectangleArea(heights))
}
return max
};
var largestRectangleArea = function (heights) {
const stack = []
const h = [0, ...heights, 0]
let max = 0
for (let i = 0; i < h.length; i++) {
while (stack.length && h[i] < h[stack[stack.length - 1]]) {
const cur = stack.pop()
max = Math.max(max, h[cur] * (i - stack[stack.length - 1] - 1))
}
stack.push(i)
}
return max
};
