Leetcode—85. 最大矩形【困难】

2025每日刷题（238）

Leetcode—85. 最大矩形

算法思想

栈怎么算 right？

当你走到 i，高度是 h：

如果 h 比栈顶高度小（或相等），说明：

栈顶那个柱子 top 右边第一次遇到更矮的，就是现在的 i

所以立刻确定：right[top] = i

然后弹出 top，一直弹到栈顶比 h 小为止（保持递增）

所以 right[…] 都是在“出栈”的那一刻确定的。

栈怎么算 left？

当弹栈结束后：

如果栈不空，新的栈顶就是左边离 i 最近且更矮的柱子下标

left[i] = stk[top]

如果栈空，说明左边没有更矮的

left[i] = -1

所以 left[i] 是在“入栈前”通过栈顶直接得到的。

单调栈实现代码

func maximalRectangle(matrix [][]byte) int {
n := len(matrix[0])
heights := make([]int, n)
ans := 0
for _, row := range matrix {
for j, c := range row {
if(c == '1') {
heights[j]++
} else {
heights[j] = 0
}
}
ans = max(ans, largeArea(heights))
}
return ans
}

func largeArea(height []int) int {
n := len(height)
stk := make([]int, 0)
left, right := make([]int, n), make([]int, n)
for i := range n {
right[i] = n
}

for i, h := range height {
for len(stk) > 0 && height[stk[len(stk) – 1]] >= h {
right[stk[len(stk) – 1]] = i
stk = stk[:len(stk) – 1]
}
if(len(stk) > 0) {
left[i] = stk[len(stk) – 1]
} else {
left[i] = –1
}
stk = append(stk, i)
}

res := 0
for i := range n {
res = max(res, height[i] * (right[i] – left[i] – 1))
}
return res
}

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！