放置盒子【LC1739】
有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：
- 你可以把盒子放在地板上的任何地方。
- 如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量*。*
只能找找规律 求和肯定算不出来
找规律+贪心
- 思路：
。首先贪心放置盒子使接触地面的盒子数量最小的情况下，放置更多的盒子
- 局部最优：每次放置盒子优先放置在顶部，顶部不能放置再放在底部
- 全局最优：接触地面的盒子数量最小的情况下，放置最多的盒子
。按照此种方式放置盒子的话，每层能够放置的盒子存在特殊规律：
- 第i 层最多可以增加i 个接触地面的盒子，能够增加的盒子个数为i ∗ ( i + 1 )/2
- 底部每增加第k个盒子时，一共可以增加的盒子数量为k【底部+上方一共可以增加的】
。因此首先将前i−1填满，然后求出还需要在底部放置j个盒子，再可以填充n个盒子
- 实现
。首先使用cur表示第i层最多可以增加多少个可放置的盒子，如果n>cur，那么n 递减cur，并且cur每次递增i个
。然后第需要在添加几个接触地面的盒子，才能够放置n个盒子
class Solution { public int minimumBoxes(int n) { int i = 1, cur = 1; while (cur < n){ n -= cur; i++; cur += i; } int j = 1; while (n - j > 0 ){ n -= j; j++; } return i * (i - 1) / 2 + j; } }
。复杂度
- 时间复杂度：
，需要遍历每一层计算盒子数，层数 i与 n 的关系是
- 空间复杂度：O ( 1 )
二分查找
- 思路：使用二分查找法搜索需要放置至第i层（前i−1层铺满），还需要放置j个盒子至地面才可以放置n个盒子
。在第i 层放j 个放置地面的盒子，所增加的盒子总数为
。放满前i ii层的盒子总数为
。以上两个函数均具有单调性，因此可以使用二分查找进行查找
- 实现
class Solution { public int minimumBoxes(int n) { int i = 0, j = 0; int low = 1, high = Math.min(n, 100000); while (low < high) { int mid = (low + high) >> 1; long sum = (long) mid * (mid + 1) * (mid + 2) / 6; if (sum >= n) { high = mid; } else { low = mid + 1; } } i = low; n -= (long) (i - 1) * i * (i + 1) / 6; low = 1; high = i; while (low < high) { int mid = (low + high) >> 1; long sum = (long) mid * (mid + 1) / 2; if (sum >= n) { high = mid; } else { low = mid + 1; } } j = low; return (i - 1) * i / 2 + j; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/building-boxes/solutions/2030450/fang-zhi-he-zi-by-leetcode-solution-7ah2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(log(n))
- 空间复杂度：O ( 1 )
