← 返回编程题库
coding-largest-rectangle-order-book-depth困难免费版2000ms未尝试

订单簿深度中的最大可执行矩形

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]) -> intdepths 是一段沿价格方向排列的非负整数挂单量序列。返回一个 int,等于最大矩形面积 max over (l, r, h) of h * (r - l + 1),约束 0 ≤ l ≤ r < nh ≤ 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 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

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。这是这道题的关键边界。