面试题库 › 客户端 › 区间最小值乘区间和的最大值

区间最小值乘区间和的最大值

难度 ★★★在 1 场真实面经中被问到 方向:客户端考点:栈与队列

哪些公司问过

字节跳动1

常见岗位:C++ / Qt 客户端

答案要点

  1. 枚举每个元素作为区间最小值,单调栈求左右第一个更小元素
  2. 前缀和 O(1) 计算区间和,全非负时取最宽区间,整体 O(n)
  3. 有负数时,最小值为负要让区间和尽量小,需配合区间最值查询
  4. 单调栈存下标,相等元素一侧严格一侧非严格避免遗漏
  5. 乘积和前缀和使用 64 位整型防溢出

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题