哎你说“最大矩形”我第一反应不是刷题哈,是那种线上一张图表…柱状图那种,老板盯着看“哪个时段峰值最大”,然后你写个统计一算,咔,算错了,峰值没错,面积错了……就很尴尬,你懂吧,就是那个“柱状图里最大的矩形面积”这题(很多人叫它最大矩形)
我当年就栽在一个细节上:你以为高度一变就结束了,结果右边还有更小的柱子把你“结算”给触发了,所以最稳的套路就是:单调栈,栈里放下标,保证对应高度递增;一旦来了个更矮的,就把栈顶弹出,弹出的那个高度当“矩形高度”,左右边界用“当前下标 i”当右边界,用“弹完后的栈顶”当左边界(左边界是那个更矮的柱子位置),宽度就是 i - left - 1。对了,最后别忘了“哨兵”,不然最后一段递增的柱子你没机会结算,很多人就卡这。
下面我直接给你一份 PHP 的源码,能跑,写得比较糙但实用(我就按我平时写业务脚本那味儿来):
<?php/** * 柱状图最大矩形面积 * @param int[] $heights * @return int */functionlargestRectangleArea(array $heights): int{// 哨兵:两边各加一个 0,强制把栈清空结算掉 array_unshift($heights, 0); $heights[] = 0; $stack = []; // 存下标,保证对应高度递增 $maxArea = 0; $n = count($heights);for ($i = 0; $i < $n; $i++) {// 当前高度比栈顶小 -> 结算while (!empty($stack) && $heights[$i] < $heights[end($stack)]) { $topIndex = array_pop($stack); $h = $heights[$topIndex];// 弹出后新的栈顶就是“左侧第一个更矮”的位置 $leftIndex = empty($stack) ? -1 : end($stack); $width = $i - $leftIndex - 1; $area = $h * $width;if ($area > $maxArea) $maxArea = $area; } $stack[] = $i; }return $maxArea;}// 随便跑几个例子$cases = [ [2,1,5,6,2,3], // 10 [2,4], // 4 [1,1,1,1], // 4 [4,3,2,1], // 6 [], // 0];foreach ($cases as $arr) {echo json_encode($arr) . " => " . largestRectangleArea($arr) . PHP_EOL;}
你注意哈,这里面两个很容易“语音转文字式翻车”的点我给你点一下(我以前就嘴硬不信,后来真翻车了):
- 宽度不是
i - topIndex,也不是 i - leftIndex,是 i - leftIndex - 1,少那个 1 面积直接飘 - 左边界取的是“弹完后的栈顶”,不是弹出的那个;弹出的那个已经是高度本体了,你要的是它左边第一个更矮的柱子位置
复杂度就很舒服,O(n),每个下标最多进栈出栈一次,线上跑大数组也不虚。
你要是说的不是柱状图,而是那个二维 0/1 矩阵的“最大矩形”(LeetCode 85 那个),也能用这套:每一行当底,把连续 1 累成高度数组,然后每行跑一遍我上面这个函数就行……不过你先按柱状图这个搞,八成你说的就是它