笔试真题复盘：区间最小值乘区间和，怎么求全局最大值

深蓝黑背景封面：右侧大标题「区间最小值 × 区间和，怎么求全局最大值」，副标题「单调栈定边界，前缀和算区间和」；左侧是数组 3、1、6、4、5、2 的柱状图，以元素 4 为最小值的柱被紫色高亮，左右两支箭头从它出发向外扩展，分别停在左侧第一个更小的 1 和右侧第一个更小的 2 之前，上方括号标注「以 4 为最小值能覆盖的最远区间 [6,4,5]」；图下方给出该候选的核算「min 4 × sum 15 = 60」。左上标注「笔试复盘 · 算法」，右上胶囊标注「Day 07 · 11-14」图 1：本文封面，以元素 4 为最小值向两侧扩展管辖区间的过程。

先说明属性：这是一篇笔试真题复盘，题目出自本地历史笔试资料，与任何公司的当前招聘无关。题目本身一句话：给定一个元素都在 0 到 100 之间的数组，选一个区间，使「区间最小值 × 区间所有数的和」最大，输出这个最大值。数组长度最大 50 万。题面给的例子是 [6,2,1]：六个区间的计算值分别是 [6]=36、[2]=4、[1]=1、[6,2]=16、[2,1]=3、[6,2,1]=9，答案是 36。

暴力枚举卡在哪。

区间一共有 n(n+1)/2 个，n 取 50 万时约 1250 亿个，两重循环必然超时。但把题面例子的六个值列一遍，能看出一个结构：每个区间都有自己的最小值，乘积由「最小值」和「长度」共同决定。这提示换个枚举对象——不按区间枚举，按「谁当最小值」分类：每个元素当最小值时，它最远能管多大的区间？

关键转化：最小值的管辖区间。

对元素 a[i]，它能作为最小值覆盖的最远区间是确定的：左边界停在左侧第一个比它小的元素处，右边界停在右侧第一个比它小的元素处（边界都取开区间，越界则最小值易主）。因为元素全部非负，固定最小值后区间越长、和越大，所以每个元素的最优候选就是「a[i] × 它的最大管辖区间之和」。全局答案 = 所有候选的最大值。问题于是拆成两件小事：快速求每个元素的左右边界，快速求任意区间和。

单调栈定边界，前缀和算区间和。

维护一个「栈底到栈顶递增」的下标栈，从左往右扫：新元素 a[i] 比栈顶对应的值小时，栈顶元素的右界就是 i（它右侧第一个更小的值），弹出后新的栈顶就是它的左界。每个下标入栈、出栈各一次，O(n) 拿到全部边界。区间和交给前缀和数组 P：区间 [l,r] 的和 = P[r+1] − P[l]，O(1) 一次。

用 Node.js 22 实现并与 O(n²) 暴力对拍：

function maxMinMulSum(a) {
  const n = a.length, P = [0];
  for (let i = 0; i < n; i++) P[i + 1] = P[i] + a[i];
  const left = new Array(n), right = new Array(n), st = [];
  for (let i = 0; i < n; i++) {           // 左界：左侧第一个严格更小
    while (st.length && a[st[st.length - 1]] >= a[i]) st.pop();
    left[i] = st.length ? st[st.length - 1] : -1;
    st.push(i);
  }
  st.length = 0;
  for (let i = n - 1; i >= 0; i--) {      // 右界：右侧第一个更小或相等
    while (st.length && a[st[st.length - 1]] > a[i]) st.pop();
    right[i] = st.length ? st[st.length - 1] : n;
    st.push(i);
  }
  let best = 0;
  for (let i = 0; i < n; i++)
    best = Math.max(best, a[i] * (P[right[i]] - P[left[i] + 1]));
  return best;
}
console.log(maxMinMulSum([6, 2, 1]));          // 36，题面例子
console.log(maxMinMulSum([3, 1, 6, 4, 5, 2])); // 60
console.log(maxMinMulSum([0, 0, 0]));          // 0
console.log(maxMinMulSum([100]));              // 10000

四组输出与预期一致；再用随机小规模数组（含重复值和 0）与暴力枚举对拍两万组，全部一致。

图 2：边界规则、单调栈过程与前缀和公式，最大值 60 来自区间 [6,4,5]。

手工走一遍概念图里的例子。

数组 3、1、6、4、5、2，看元素 4（下标 3）：左侧第一个更小的是下标 1 的 1，右侧第一个更小的是下标 5 的 2，所以管辖区间是 [2,4]，即子数组 [6,4,5]，区间和 15，候选值 4×15=60。扫完全部六个候选，60 最大，答案 60——这个例子比题面例子更能体现「长区间 × 中等最小值」击败「短区间 × 大最小值」的权衡。

两个容易写错的细节。

一是相等元素的归属：代码里左扫弹「大于等于」、右扫只弹「大于」，保证一段相等元素恰好被其中一个代表完整接管，不重不漏——两边都用同一种比较，要么重复计算要么漏掉候选。二是别省略对拍：单调栈的错误几乎都藏在边界和相等处理里，肉眼看不出来，跑两万组随机对拍最诚实。

顺带一提，「以每个元素为中心向两侧扩展贡献区间」是直方图最大矩形等一系列题目的同一副骨架，单调栈模板在 knowledge 延伸篇里有专门梳理。

回到笔试现场，建议的答题结构：先确认题意和数据规模，指出暴力 O(n²) 超时；再给出「按最小值分类」的转化并论证管辖区间为什么取到最远（元素非负是前提）；然后讲单调栈定边界与前缀和求和，报出 O(n) 时间、O(n) 空间；最后主动补相等元素与全零数组的边界处理。你在写单调栈时踩过相等元素的坑吗？当时是对拍拍出来的还是线上挂出来的？

笔试真题复盘：区间最小值乘区间和，怎么求全局最大值

相关阅读