哎我跟你说“最大矩形”这题吧，面试官嘴上就四个字，实际背后就两套常见版本…一个是柱状图那个（LeetCode 84 那味儿），另一个是二进制矩阵里找全 1 最大矩形（LeetCode 85）。你要是只写一套，刚好对面问另一套，你就…嗯，懂的。
我就按我平时在工位上被人打断三次、咖啡都凉了那种节奏，直接把两套 Go 代码都给你，反正核心都靠“单调栈”，就像你线上看 QPS 图一样：一旦出现“比我矮的柱子”，就得开始结算面积了。
先来柱状图最大矩形（输入 heights[]），这个最像“仓库堆箱子”，突然来了个矮箱子，前面高箱子就得结账。
package mainimport ("fmt")funclargestRectangleArea(heights []int)int { n := len(heights)// 栈里放下标，保证 heights[stack] 单调递增 stack := make([]int, 0, n+2)// 两边加哨兵：左边 -1，右边补一个 0 高度用来清空栈 stack = append(stack, -1) best := 0for i := 0; i <= n; i++ { curH := 0if i < n { curH = heights[i] }// 只要当前高度比栈顶高度小，就开始弹栈结算forlen(stack) > 1 { top := stack[len(stack)-1]if top == -1 || heights[top] <= curH {break }// 弹出一个“最高点”，计算它作为最矮边时的最大宽度 h := heights[top] stack = stack[:len(stack)-1] leftLessIdx := stack[len(stack)-1] // 弹完后的栈顶，就是左边第一个更矮的 width := i - leftLessIdx - 1// 右边界 i(更矮) 不含，左边界 leftLessIdx 不含 area := h * widthif area > best { best = area } } stack = append(stack, i) }return best}
然后是“矩阵最大矩形”（0/1 矩阵），这个就很像你每天看日志：一行一行扫，把连续的 1 当成“高度”累加，等于每一行都生成一个柱状图，然后每行跑一次上面那个函数就完事了…就这么朴素，离谱但好用。
funcmaximalRectangle(matrix [][]byte)int {iflen(matrix) == 0 || len(matrix[0]) == 0 {return0 } rows, cols := len(matrix), len(matrix[0]) heights := make([]int, cols) best := 0for r := 0; r < rows; r++ {// 更新这一行对应的“柱状图高度”for c := 0; c < cols; c++ {if matrix[r][c] == '1' { heights[c] += 1 } else { heights[c] = 0 } }// 这一行当底边，求一次柱状图最大矩形 area := largestRectangleArea(heights)if area > best { best = area } }return best}
我怕你说“东哥你光给函数我怎么跑”，行，我给个 main，顺便带俩例子，别到时候你在本地一跑没输出又来问我“是不是 Go 版本问题”…不是，真不是。
funcmain() {// 84：柱状图 fmt.Println(largestRectangleArea([]int{2, 1, 5, 6, 2, 3})) // 10// 85：矩阵 m := [][]byte{ []byte("10100"), []byte("10111"), []byte("11111"), []byte("10010"), } fmt.Println(maximalRectangle(m)) // 6}
你看这两套其实就一个套路： 矩阵那题就是“每行把自己当底边”，把上方连续的 1 累成 heights，然后扔给柱状图最大矩形去算。时间复杂度也挺规矩：矩阵是 O(R*C)，柱状图是 O(n)。
对了，你要是准备面试，面试官经常会突然补一句：“你这个栈里为啥放下标不放高度？”——你就说宽度要算边界，下标更方便，放高度你还得回头找位置，越写越像线上修 bug，越修越大…行了我不扯了。
