放置盒子【LC1739】

有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：

• 你可以把盒子放在地板上的任何地方。
• 如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。

给你一个整数 n ，返回接触地面的盒子的 最少 可能数量*。*

只能找找规律 求和肯定算不出来

找规律+贪心

• 思路：

  • 首先贪心放置盒子使接触地面的盒子数量最小的情况下，放置更多的盒子
    • 局部最优：每次放置盒子优先放置在顶部，顶部不能放置再放在底部
    • 全局最优：接触地面的盒子数量最小的情况下，放置最多的盒子
  • 按照此种方式放置盒子的话，每层能够放置的盒子存在特殊规律：
    • 第iii层最多可以增加iii个接触地面的盒子，能够增加的盒子个数为i∗(i+1)2\frac{i*(i+1)}{2}2i∗(i+1)​
    • 底部每增加第kkk个盒子时，一共可以增加的盒子数量为kkk【底部+上方一共可以增加的】
  • 因此首先将前i−1i-1i−1填满，然后求出还需要在底部放置jjj个盒子，再可以填充nnn个盒子

• 实现

  • 首先使用curcurcur表示第iii层最多可以增加多少个可放置的盒子，如果n>curn>curn>cur，那么nnn递减curcurcur，并且curcurcur每次递增iii个
  • 然后第需要在添加几个接触地面的盒子，才能够放置nnn个盒子

  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;}
  }
  

  • 复杂度
    • 时间复杂度：O(n3)O(\sqrt[3] n)O(3n​)，需要遍历每一层计算盒子数，层数 iii与 nnn 的关系是i=O(n3)i = O(\sqrt[3]{n})i=O(3n​)
    • 空间复杂度：O(1)O(1)O(1)

二分查找

• 思路：使用二分查找法搜索需要放置至第iii层（前i−1i-1i−1层铺满），还需要放置jjj个盒子至地面才可以放置nnn个盒子

  • 在第iii层放jjj个放置地面的盒子，所增加的盒子总数为
    f(j)=j∗(j+1)2j≤if(j)= \frac{j*(j+1)}{2}\\ j \le i f(j)=2j∗(j+1)​j≤i

  • 放满前iii层的盒子总数为
    g(i)=∑n=1if(n)=12∑n=1i(n2+n)=12∑n=1i[n∗(n+1)∗(2n+1)6+n(n+1)2]=∑n=1in∗(n+1)∗(n+2)6g(i) = \sum_{n=1} ^if(n)=\frac{1}{2}\sum_{n=1} ^i(n^2+n)\\ = \frac{1}{2}\sum_{n=1} ^i[\frac{n*(n+1)*(2n+1)}{6}+\frac{n(n+1)}{2}]\\ =\sum_{n=1} ^i\frac{n*(n+1)*(n+2)}{6} g(i)=n=1∑i​f(n)=21​n=1∑i​(n2+n)=21​n=1∑i​[6n∗(n+1)∗(2n+1)​+2n(n+1)​]=n=1∑i​6n∗(n+1)∗(n+2)​

  • 以上两个函数均具有单调性，因此可以使用二分查找进行查找

• 实现

  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(log(n))O(log(n))
    • 空间复杂度：O(1)O(1)O(1)