砍树问题(二分答案)
哪些公司问过
答案要点
- 识别二分答案:H 越高砍得越少,木材量随 H 单调不增
- check(H):累加 max(0, h_i − H),判断是否 ≥ M
- 区间 [0, max h];满足条件记录答案并向右收缩,否则向左
- 累加用 long 防溢出,时间 O(n log maxH)
- 通用框架:目标量随二分变量单调即可套用,只需替换 check
易错点
- 累加木材用 int 导致溢出
- 二分边界更新写成 left = mid,导致死循环
- 把求最大 H 写成求最小 H,方向弄反
面试官常见追问
- 二分答案适用的条件是什么?
- 能不排序直接做吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。