刷题避坑指南：LeetCode风格‘栅栏问题’的两种易错思路与正确解法（Java版）

在算法面试和编程竞赛中，"栅栏问题"这类资源分配题目看似简单，却暗藏多个思维陷阱。许多候选人在面对这类需要计算最小排数的问题时，往往因为忽略边界条件或采用错误策略而失分。本文将深入剖析两种高频错误解法，并给出经过实战检验的正确实现方案。

1. 问题本质与常见误区

栅栏问题的核心在于动态宽度计算与资源分配。给定n个人、栅栏高度h和道路宽度w，每个人正常行走宽度为1，若身高超过h则需弯腰行走宽度变为2。我们需要计算最少需要多少排才能容纳所有人。

1.1 误区一：先排序再贪心

许多初学者会尝试先对身高进行排序，然后尝试将高个子集中放置：

// 错误示范：排序后贪心
Arrays.sort(heights);
int currentRowWidth = 0;
int rows = 1;
for (int height : heights) {
    int width = height > h ? 2 : 1;
    if (currentRowWidth + width > w) {
        rows++;
        currentRowWidth = width;
    } else {
        currentRowWidth += width;
    }
}

这种解法的问题在于：

• 排序打乱了原始顺序，可能导致非最优解
• 没有考虑"全弯腰"的特殊情况
• 当w=3时，两个弯腰的人(2+2=4>3)会被分到两排，但实际上他们可以站在同一排

1.2 误区二：忽略全弯腰情况

另一种常见错误是直接计算总宽度后简单除以w：

// 不完善的解法
int totalWidth = 0;
for (int height : heights) {
    totalWidth += height > h ? 2 : 1;
}
int rows = (int) Math.ceil((double)totalWidth / w);

这个版本忽略了当所有人都需要弯腰时(w=2)，实际上每人必须独占一排的特殊情况。例如输入为 3 2 2 和 [3,3,3] 时，正确输出应为3而非2。

2. 正确解法：累计宽度+特殊判断

经过多次OJ提交验证，正确的解法需要结合总宽度计算和特殊情况处理：

public static int calculateMinRows(int n, int h, int w, int[] heights) {
    int totalWidth = 0;
    boolean allBend = true;
    
    for (int height : heights) {
        if (height <= h) {
            allBend = false;
        }
        totalWidth += height > h ? 2 : 1;
    }
    
    if (allBend) {
        return n; // 每人必须独占一排
    }
    
    int minRows = totalWidth / w;
    if (totalWidth % w != 0) {
        minRows++;
    }
    return minRows;
}

2.1 关键改进点

1. 全弯腰标志位 ：通过 allBend 变量标记是否所有人都需要弯腰
2. 双重判断逻辑 ：先处理特殊场景，再计算常规情况
3. 取整技巧 ：利用整数除法和取模运算替代浮点数计算

注意：在实际面试中，建议先口头说明可能存在的边界情况，再开始编码

3. 测试用例设计技巧

针对这类问题，高质量的测试用例应覆盖以下场景：

用例类型	示例输入	预期输出	验证要点
常规混合	3 2 4 [1,3,2]	1	正常与弯腰混合
全正常	2 3 2 [1,2]	1	所有人正常行走
全弯腰	3 2 2 [3,3,3]	3	每人独占一排
边界值	1 1 1 [2]	1	单人特殊情况
刚好填满	2 2 3 [3,1]	1	总宽度等于w

4. 性能优化与进阶思考

虽然该问题时间复杂度已经是O(n)，但在实际工程应用中还可以考虑：

1. 并行计算 ：对于大规模数据，可将身高数组分块并行处理
2. 内存优化 ：使用位运算存储标志位（当n很大时）
3. 动态扩展 ：如果w是动态变化的，可以设计增量更新算法

// 并行计算版本（Java 8+）
long countNormal = Arrays.stream(heights)
                        .filter(h -> h <= fenceHeight)
                        .count();
boolean allBend = countNormal == 0;
int totalWidth = (int)(countNormal + 2*(heights.length - countNormal));

在解决类似问题时，建议养成以下习惯：

• 先列举所有可能的边界条件
• 用简单测试用例手动验证
• 考虑极端场景（如最大输入规模）
• 明确变量命名（避免使用模糊的flag1、flag2）

5. 同类问题扩展

掌握栅栏问题的解法后，可以轻松应对以下变种题目：

• 会议室安排问题（不同时长会议）
• 背包问题的简化版本
• 资源分配与调度问题

这类问题的通用解决模式是：

1. 计算总需求
2. 处理特殊约束
3. 分配可用资源
4. 向上取整计算结果

在最近的Google面试中，就出现过将栅栏问题与优先队列结合的变种题。面试官会先让候选人解决基础版本，然后逐步增加约束条件（如每排至少要有k个正常行走的人）。