订单簿深度中的最大可执行矩形
Largest Rectangle in Order Book Depth
开始编码某个限价订单簿在某个瞬间被快照了下来:从最优买价向下数,连续 n 个相邻的价格档位上,每一档挂着的总挂单量记作 depths[i](i = 0 是最贵的那一档,i = n-1 是最便宜的那一档;档位之间的价格步长是均匀的)。一支执行算法准备发出一笔单一价格的限价大单,它能"吃下"的最大总量只能是这样的形态:选一段连续的档位 [l, r] 与一个统一的深度 h,把每一档都吃 h 单位(h ≤ min(depths[l..r])),总成交量就是 h * (r - l + 1)。请返回所有合法 (l, r, h) 选择下能拿到的最大成交量——也就是这条深度阶梯里能内切出的最大矩形面积。
请实现 solution(depths: list[int]) -> int。depths 是一段沿价格方向排列的非负整数挂单量序列。返回一个 int,等于最大矩形面积 max over (l, r, h) of h * (r - l + 1),约束 0 ≤ l ≤ r < n 且 h ≤ min(depths[l..r])。depths 为空时返回 0;若所有档位都是 0,返回 0。
举例:solution([2, 1, 5, 6, 2, 3]) 应返回 10。最优形态是取下标 [2, 3] 这两档(深度分别是 5 和 6),统一吃 h = 5,面积 5 * 2 = 10。其他候选包括以 depths[3] = 6 为短板(宽度 1,面积 6)、以最末两档 [2, 3] 为短板(宽度 2,面积 4)等等,都比不上前者。再举一例:solution([3, 3, 3, 3]) 返回 12,整段平台共享 h = 3,宽度 4。这条用例同时是边界检查用的——把弹栈条件写成 >= 会把答案错成 3。
朴素解法对每对 (l, r) 算一次区间最小值,O(n²) 甚至 O(n²) 量级在 n = 10⁵ 下会跑成 10¹⁰ 次基本操作,必然超时。正确做法是单调栈:维护一个索引栈,使得栈中索引对应的 depths 单调非递减。处理第 i 个档位时,把栈顶 depths[stack[-1]] > depths[i] 的索引一一弹出,被弹出的 j 此刻刚好确定了"以 depths[j] 为短板"的最大矩形——它的右边界就是 i(右侧第一个严格更浅的档位),左边界就是弹完之后新的栈顶(左侧第一个严格更浅的档位),宽度 i - new_top - 1。在 depths 末尾追加一个 0 哨兵能优雅地把循环结束后栈里残留的索引一并结算。每个索引最多入栈、出栈各一次,整体复杂度 O(n)。
约束条件
- 0 ≤ len(depths) ≤ 100000
- 0 ≤ depths[i] ≤ 10^9,整数
- 返回值是 int;空 depths 返回 0
- 矩形面积按 `深度 * 连续档位数` 计算,等于该区间能批量吃掉的总挂单量
- 时间复杂度必须是 O(n) 摊还;O(n²) 在大用例下会超时
样例
Case 1 · statement example: classic textbook profile
输入: [[2,1,5,6,2,3]]
期望: 10
最优形态是取下标 [2, 3] 这两档(深度 5 和 6),统一吃 h = 5,面积 5 * 2 = 10。任何更宽的取法都被深度更浅的档位拖累。
Case 2 · flat plateau: strict-pop boundary
输入: [[3,3,3,3]]
期望: 12
整段平台共享 h = 3,宽度 4,面积 12。如果误把弹栈条件写成 `>=`,等高档位会被错误切分,结果会退化成 3。这是这道题的关键边界。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement example: classic textbook profile
输入: [[2,1,5,6,2,3]]
期望: 10
最优形态是取下标 [2, 3] 这两档(深度 5 和 6),统一吃 h = 5,面积 5 * 2 = 10。任何更宽的取法都被深度更浅的档位拖累。
Case 2 · flat plateau: strict-pop boundary
输入: [[3,3,3,3]]
期望: 12
整段平台共享 h = 3,宽度 4,面积 12。如果误把弹栈条件写成 `>=`,等高档位会被错误切分,结果会退化成 3。这是这道题的关键边界。