预算内运行机器人的最大连续子数组长度
哪些公司问过
答案要点
- 代价等于窗口内最大充电时间加窗口长度乘运行成本之和,窗口扩大时代价单调不减,可用滑动窗口
- 用存下标的单调递减双端队列维护窗口最大值,队头即最大值
- 超预算时收缩左边界,队头下标滑出窗口就弹出,并同步减去运行成本
- 时间 O(n)、空间 O(n);乘积用 64 位整数防止溢出
- 也可以二分答案 k,再用定长窗口最大值检查,复杂度 O(n log n)
易错点
- 用 32 位整数计算 k 乘总和导致溢出
- 收缩左边界时忘记弹出已滑出窗口的队头
- 每次重新扫描窗口求最大值,复杂度退化到 O(n²)
- 把公式理解错,k 乘的是运行成本之和,不是最大充电时间
面试官常见追问
- 为什么能用滑动窗口,而不用枚举所有子数组?
- 单调队列为什么存下标而不存值?
- 不用单调队列还有什么办法求窗口最大值?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场