千问 LeetCode 1739.放置盒子 public int minimumBoxes(int n)

这道题是 LeetCode 1739. 放置盒子，核心思路是贪心和找规律。

为了使接触地面的盒子数量最少，我们需要尽可能高效地向上堆叠。最优策略是让盒子靠墙角堆放，形成一个金字塔结构。

💡 核心思路

1. 构建完整的金字塔
我们首先尝试构建一个完整的、靠墙角的金字塔。这种堆叠方式下，每一层能放置的盒子数量遵循一个规律：
* 第 1 层（最底层）：可以放 1 个盒子。
* 第 2 层：可以放 1 + 2 = 3 个盒子。
* 第 3 层：可以放 1 + 2 + 3 = 6 个盒子。
* ...
* 第 i 层：可以放 1 + 2 + ... + i = i * (i + 1) / 2 个盒子。

我们的第一步就是找到最大的 i，使得前 i 层盒子的总数不超过 n。

2. 处理剩余的盒子
在构建了完整的 i 层金字塔后，如果还有剩余的盒子，我们需要继续在地面上添加盒子。为了用最少的地面盒子承载最多的剩余盒子，我们应该沿着已有的金字塔边缘继续添加。
* 在地面上新增第 1 个盒子，它可以支撑其上方的 1 个盒子。
* 在地面上新增第 2 个盒子，它可以支撑其上方的 2 个盒子（一个在它上面，一个在它和前一个盒子之上）。
* 在地面上新增第 j 个盒子，它可以额外支撑 j 个盒子。

我们不断在地面上增加盒子，直到能够容纳所有剩余的盒子为止。

最终的答案就是完整金字塔的底层盒子数加上为剩余盒子新增的地面盒子数。

🧮 算法步骤

1. 初始化变量，用于计算完整金字塔的层数和总盒子数。
2. 循环计算，直到再增加一层就会超过 n 个盒子。
3. 计算还剩下多少个盒子需要放置。
4. 再次循环，计算需要在地面上新增多少个盒子才能容纳剩余的盒子。
5. 返回总的地面盒子数。

💻 Java 代码实现

public class Solution {
public int minimumBoxes(int n) {
int totalBoxes = 0; // 当前已放置的盒子总数
int currentLayerBoxes = 0; // 当前层（第i层）的盒子数
int i = 0; // 当前层数

// 第一步：构建完整的金字塔
// 只要再加一层不会超过n，就继续加
while (totalBoxes + currentLayerBoxes + (i + 1) 0) {
j++;
floorBoxes++; // 地面上多放一个盒子
remainingBoxes -= j; // 这个新盒子可以支撑j个盒子（包括它自己）
}

return floorBoxes;
}
}