当前位置：首页 > news >正文

【每日一题Day67】LC1739放置盒子 | 找规律+贪心二分查找

news 来源：原创 2024/5/9 3:25:01

放置盒子【LC1739】

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

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

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

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

找规律+贪心

思路：
- 首先贪心放置盒子使接触地面的盒子数量最小的情况下，放置更多的盒子
  - 局部最优：每次放置盒子优先放置在顶部，顶部不能放置再放在底部
  - 全局最优：接触地面的盒子数量最小的情况下，放置最多的盒子
- 按照此种方式放置盒子的话，每层能够放置的盒子存在特殊规律：
  - 第 $i$ 层最多可以增加 $i$ 个接触地面的盒子，能够增加的盒子个数为 $\frac{i*(i+1)}{2}$
  - 底部每增加第 $k$ 个盒子时，一共可以增加的盒子数量为 $k$ 【底部+上方一共可以增加的】
- 因此首先将前 $i - 1$ 填满，然后求出还需要在底部放置 $j$ 个盒子，再可以填充 $n$ 个盒子
实现
- 首先使用 $c u r$ 表示第 $i$ 层最多可以增加多少个可放置的盒子，如果 $n > c u r$ ，那么 $n$ 递减 $c u r$ ，并且 $c u r$ 每次递增 $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;
    }
}
```
- 复杂度
  - 时间复杂度： $O(\sqrt[3] n)$ ，需要遍历每一层计算盒子数，层数 $i$ 与 $n$ 的关系是 $O(\sqrt[3]{n})$
  - 空间复杂度： $O (1)$

二分查找

思路：使用二分查找法搜索需要放置至第 $i$ 层（前 $i - 1$ 层铺满），还需要放置 $j$ 个盒子至地面才可以放置 $n$ 个盒子
- 在第 $i$ 层放 $j$ 个放置地面的盒子，所增加的盒子总数为
  $\frac{j*(j+1)}{2}\\ j \le i$
- 放满前 $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}$
- 以上两个函数均具有单调性，因此可以使用二分查找进行查找

实现

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。