面试题库 › C++ / 后端 › 预算内运行机器人的最大连续子数组长度

预算内运行机器人的最大连续子数组长度

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

哪些公司问过

英伟达1

常见岗位:自动驾驶

答案要点

  1. 代价等于窗口内最大充电时间加窗口长度乘运行成本之和,窗口扩大时代价单调不减,可用滑动窗口
  2. 用存下标的单调递减双端队列维护窗口最大值,队头即最大值
  3. 超预算时收缩左边界,队头下标滑出窗口就弹出,并同步减去运行成本
  4. 时间 O(n)、空间 O(n);乘积用 64 位整数防止溢出
  5. 也可以二分答案 k,再用定长窗口最大值检查,复杂度 O(n log n)

易错点

面试官常见追问

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

相关面试题