一般是用来找离当前元素(左端/右段)最近的比它(大/小)的(位置/元素)。
-
如果是找左边/右边最近的比cur要大的数,则从左到右遍历,整体的stack应该是单调递增的(从栈顶到栈底)(相当于压入的元素只能越来越小),如果栈顶 <= cur,则弹出,压入当前元素
-
如果是找左边/右边最近的比cur要小的数,则从左到右遍历,整体的stack应该是单调递减的(从栈顶到栈底)(相当于压入的元素只能越来越大),如果栈顶 >= cur,则弹出,压入当前元素
假设当前从栈顶弹出的元素为x(下标),则
- 在栈中位于x位置下面的元素即:离x左边最近且符合条件的位置。
- 当前遍历到的位置即:离x右边最近且符合条件的位置。
即 [左,x] <- 右 这种感觉
LC 739. 每日温度
有两种写法。
var dailyTemperatures = function(temperatures) {
const stack = []
const res = []
const N = temperatures.length
// 从右到左,把下一个更大的数存起来,每次都拿当前数和栈顶做比较,更新当前数的答案
for(let i = N - 1; i >= 0; i--){
while(stack.length && temperatures[i] >= temperatures[stack[stack.length - 1]]){
const t = stack.pop()
}
if(stack.length){
res[i] = stack[stack.length - 1] - i
}else{
res[i] = 0
}
stack.push(i)
}
return res
};
var dailyTemperatures = function(temperatures) {
const stack = []
const n = temperatures.length
const res = new Array(n).fill(0)
// 从左到右,把还没有发现下一个更大的数存起来,一旦发现比栈顶更大的元素,立刻更新栈顶的答案
for(let i = 0; i < n; i++){
while(stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]){
const t = stack.pop()
res[t] = i - t
}
stack.push(i)
}
return res
};
var trap = function(height) {
const stack = []
const n = height.length
let res = 0
for(let i = 0; i < n; i++){
// 从左到右,找到离自己最近的比自己大的数
while(stack.length && height[i] >= height[stack[stack.length - 1]]){
// 如果柱子i大于等于自己,则现将自己弹出
const cur = stack.pop()
if(stack.length){
const top = stack[stack.length - 1]
const l = i - top - 1 // U型的底部长度
// height[top]是左边最近比cur大的数(U型的左边界),height[i]是右边最近的比cur大的数(U型的右边界)
const h = Math.min(height[i], height[top]) - height[cur]
res += h * l
}
}
stack.push(i)
}
return res
};
var largestRectangleArea = function(heights) {
const n = heights.length
const left = new Array(n).fill(-1)
const right = new Array(n).fill(n)
let res = -Infinity
const stack = []
for(let i = 0; i < n; i++){
while(stack.length && heights[i] < heights[stack[stack.length - 1]]){
const t = stack.pop()
right[t] = i
left[t] = stack.length ? stack[stack.length - 1] : -1
}
stack.push(i)
}
while(stack.length){
const t = stack.pop()
right[t] = n
left[t] = stack.length ? stack[stack.length - 1] : -1
}
for(let i = 0; i < n; i++){
res = Math.max(res, (right[i] - left[i] - 1) * heights[i])
}
return res
};
var maximalRectangle = function(matrix) {
const m = matrix.length
const n = matrix[0].length
const heights = new Array(n).fill(0)
const calcMax = (heights) => {
const stack = []
let res = 0
// 对于每根柱子找到左、右两边第一个比它小的height,则他的面积即 (right - left - 1) * height[i]
for(let i = 0; i < heights.length; i++){
while(stack.length && heights[i] <= heights[stack[stack.length - 1]]){
const t = stack.pop()
const left = stack.length ? stack[stack.length - 1] : -1
const right = i
// 计算对于当前t节点,他能达到的最大面积
res = Math.max(res, (right - left - 1) * heights[t])
}
stack.push(i)
}
while(stack.length){
const t = stack.pop()
const left = stack.length ? stack[stack.length - 1] : -1
const right = heights.length
// 计算对于当前t节点,他能达到的最大面积
res = Math.max(res, (right - left - 1) * heights[t])
}
return res
}
let res = 0
for(let i = 0; i < m; i++){
// 更新每一层,以当前行为底边,每个col有连续1的高度
for(let j = 0; j < n; j++){
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0
}
// 针对每一层做单调栈的求最大面积
res = Math.max(res, calcMax(heights))
}
return res
};
var maximalRectangle = function(matrix) {
const m = matrix.length
const n = matrix[0].length
const heights = new Array(n).fill(0)
const calcMax = (heights) => {
let res = 0
const n = heights.length
const left = [] // left[i]表示左边离i最近比height[i]小的idx
let stack = []
for(let i = 0; i < n; i++){
while(stack.length && heights[i] <= heights[stack[stack.length - 1]]){
stack.pop()
}
left[i] = stack.length ? stack[stack.length - 1] : -1 // -1代表左边界
stack.push(i)
}
stack = []
const right = [] // right[i]表示右边离i最近比height[i]小的idx
for(let i = n - 1; i >= 0; i--){
while(stack.length && heights[i] <= heights[stack[stack.length - 1]]){
stack.pop()
}
right[i] = stack.length ? stack[stack.length - 1] : n // n代表右边界
stack.push(i)
}
// 最后再根据right + left 两边界去计算max面积
for (let i = 0; i < n; i++) {
res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
}
return res
}
let res = 0
for(let i = 0; i < m; i++){
// 更新每一层,以当前行为底边,每个col有连续1的高度
for(let j = 0; j < n; j++){
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0
}
// 针对每一层做单调栈的求最大面积
res = Math.max(res, calcMax(heights))
}
return res
};
var canSeePersonsCount = function(heights) {
const n = heights.length
const res = new Array(n).fill(0)
const stack = []
// 从右向左遍历
for(let i = n - 1; i >= 0; i--){
while(stack.length && heights[i] >= heights[stack[stack.length - 1]]){
stack.pop()
res[i] += 1
}
if(stack.length){
res[i] += 1
}
stack.push(i)
}
return res
};
var canSeePersonsCount = function(heights) {
const n = heights.length
const res = new Array(n).fill(0)
const stack = []
// 从左向右遍历
for(let i = 0; i < n; i++){
while(stack.length && heights[i] >= heights[stack[stack.length - 1]]){
const t = stack.pop()
res[t] += 1
}
if(stack.length){
res[stack[stack.length - 1]] += 1
}
stack.push(i)
}
return res
};
var nextLargerNodes = function(head) {
const stack = []
const res = []
for(let i = head, idx = 0; i; i = i.next, idx++){
while(stack.length && i.val > stack[stack.length - 1][1]){
const [idx] = stack.pop()
res[idx] = i.val
}
stack.push([idx, i.val])
}
while(stack.length){
const [idx] = stack.pop()
res[idx] = 0
}
return res
};