Qwen3.5-Plus LintCode 319 · 方阵排队 public int maxPeopleNumber(int[] height)

这是 LintCode 319 · 方阵排队 的解题思路和代码实现。

题目解析
目标：从给定的身高数组 height 中选出尽可能多的人，组成一个 k times k 的方阵（即总人数为 k^2）。
约束条件：方阵中每一行的人，其身高最大值与最小值的差不能超过 2（即 max(row) – min(row) le 2）。
注意：题目只要求“每一行”满足条件，不同行之间的身高范围可以完全不同。

核心思路
排序：首先将身高数组从小到大排序。排序后，身高相近的人会聚集在一起，方便我们寻找满足条件的连续区间。
滑动窗口（双指针）：
我们要找到一个最长的连续子数组（窗口），使得窗口内的最大值（右端点）与最小值（左端点）之差 le 2。
在这个窗口内，所有人都可以互相搭配组成行。因为窗口内任意取 k 个人（只要 k le 窗口长度），由于整体极差 le 2，这 k 个人的极差必然也 le 2，从而可以组成一行。
如果窗口长度为 L，那么这个窗口内最多能凑出 L 个人参加方阵（实际上是可以组成多行，但为了简化逻辑，我们可以直接看全局）。
修正理解：题目是选出一部分人组成一个 k times k 方阵。这意味着我们需要总共 k^2 个人。
由于不同行之间没有约束，我们可以把整个数组切分成多个满足“极差 le 2”的连续段。
对于每一个满足条件的连续段（长度为 len），它最多能贡献 len 个人进入方阵吗？
是的。因为在这个段里，任意 k 个人组成的行都满足条件。
但是，我们要组成的是一个 k times k 的方阵。这意味着我们需要从这些段里总共凑出 k^2 个人。
等等，重新审题：“请你选出一部分人组成方阵…并且每一行的人的身高差不超过2”。
这意味着：我们将选出的 k^2 个人分成 k 组（每组 k 人），每组内部极差 le 2。
贪心策略：排序后，我们尽量让身高接近的人在一行。
我们可以遍历排序后的数组，使用滑动窗口找到所有满足 height[right] – height[left] = n) {
break; // 剩余人数不足 k 人
}

        // 检查这 k 个人的极差
        // 因为数组已排序，极差 = height[i + k - 1] - height[i]
        if (height[i + k - 1] - height[i] = k) {
            return true;
        }
    }
    return countRows >= k;
}

}

逻辑验证
假设输入 [2, 5, 4, 5]，排序后 [2, 4, 5, 5]。
尝试 k=2: 需要 2 行，每行 2 人。
i=0: 检查 [2, 4] (索引 0~1)。极差 4-2=2 le 2。满足！countRows=1, i 变为 2。
i=2: 检查 [5, 5] (索引 2~3)。极差 5-5=0 le 2。满足！countRows=2, i 变为 4。
countRows (2) >= k (2)。返回 true。
结果 2 times 2 = 4。正确。

假设输入 [1, 4, 5, 6, 7, 7, 7, 10, 11, 12]，排序后同上（原样）。N=10。
尝试 k=3: 需要 3 行，每行 3 人。
i=0: [1, 4, 5], 极差 5-1=4 > 2。失败。i++ -> 1。
i=1: [4, 5, 6], 极差 6-4=2 le 2。成功。count=1, i=4。
i=4: [7, 7, 7], 极差 0。成功。count=2, i=7。
i=7: [10, 11, 12], 极差 2。成功。count=3, i=10。
count (3) >= k (3)。返回 true。
结果 3 times 3 = 9。正确。

复杂度
时间复杂度: O(N log N)。排序占主导，二分查找中的 check 函数是线性的 O(N)，二分次数是 O(log sqrt{N})，总体非常高效。
空间复杂度: O(1) (如果不考虑排序的栈空间) 或 O(log N) (排序开销)。

这个解法能够处理 N=10^5 的数据规模。