面试官爱考的‘栅栏排队’算法题：用Java实现时，90%的人会忽略这个边界条件

当你面对这道看似简单的"栅栏排队"算法题时，是否曾自信满满地写下几行代码，却在面试官的追问下发现漏洞百出？这道题之所以成为大厂面试的常客，正是因为它能精准考察候选人的 基础算法能力 和 边界条件敏感度 。今天，我们就来拆解这道题的陷阱与解法。

1. 问题本质与核心考察点

这道题表面上是计算最小排数，实则暗藏三个考察维度：

1. 贪心算法的应用 ：如何用最直观的方式分配空间
2. 整数除法的边界处理 ： totalWidth / w 的余数如何处理
3. 极端情况的防御性编程 ：当所有身高都超过栅栏时的特殊处理

许多候选人会直接写出这样的"通用解法"：

int minRows = totalWidth / w;
if (totalWidth % w != 0) minRows++;

但忽略了当 flag == 0 时（即所有人身高>h），每排只能站一人这个致命边界。面试官期待的满分答案应该包含以下防御逻辑：

if (allExceedH) {
    minRows = n; // 每人独占一排
} else {
    minRows = (totalWidth + w - 1) / w; // 优雅的向上取整写法
}

2. 代码实现中的五个致命陷阱

在实际编码中，这些细节会让90%的候选人翻车：

1. 输入读取顺序错误 ：先读n,h,w还是先读数组？

   // 错误示范：遗漏了先读取n,h,w的逻辑
   int[] heights = new int[n]; // 此时n还未初始化！
   

2. 变量初始化问题 ： totalWidth 未初始化为0导致累加错误

3. 边界标记逻辑缺陷 ：用 flag 标记是否有<=h的人，但初始值应为0还是1？

4. 整数除法取整误区 ：以下两种写法哪种更优？

   // 方案A
   int minRows = (totalWidth + w - 1) / w;
   
   // 方案B
   int minRows = totalWidth / w;
   if (totalWidth % w != 0) minRows++;
   

5. 特殊条件判断遗漏 ：未处理 w == 0 的非法输入（虽然题目保证w>0）

3. 面试中的加分项：测试用例设计

优秀的候选人会主动讨论测试用例，例如：

4. 算法优化与空间复杂度

虽然本题时间复杂度已经是O(n)，但可以讨论：

1. 提前终止优化 ：当检测到 allExceedH 时立即返回n
2. 并行计算优化 ：使用Java 8 Stream并行处理大数据量

   boolean allExceed = Arrays.stream(heights).allMatch(v -> v > h);
   if (allExceed) return heights.length;
   

3. 内存优化 ：不需要存储所有身高，可以实时处理

   for (int i = 0; i < n; i++) {
       int height = scanner.nextInt();
       // 即时处理...
   }
   

5. 从题目延伸的面试技巧

这道题反映出的面试策略：

1. 先写主干再补边界 ：不要一开始就追求完美代码
2. 主动陈述思考过程 ："这里我需要考虑三种情况..."
3. 询问约束条件 ："请问输入规模有多大？需要处理负数吗？"
4. 展示代码风格 ：良好的变量命名和注释

   // Good
   int personCount = scanner.nextInt();
   
   // Bad
   int a = scanner.nextInt();
   

在真实的面试场景中，我曾见过候选人因为忽略 allExceedH 的情况直接挂掉面试，也见过有人通过主动讨论测试用例获得加分。这道题的巧妙之处就在于它用简单的题干隐藏了多个考察层次，这正是大厂面试题的典型特征。