Hard

题目描述

你有一个立方体储藏室，房间的宽度、长度和高度都等于 n 个单位。你需要在这个房间里放置 n 个盒子，每个盒子都是边长为 1 个单位的立方体。但是放置盒子有一些规则：

  • 你可以在地板上的任何地方放置盒子。
  • 如果盒子 x 放在盒子 y 的上面，那么盒子 y 的四个垂直边的每一边都必须与另一个盒子或墙壁相邻。

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

示例 1：

输入：n = 3
输出：3
解释：上图是三个盒子的放置方式。
这些盒子放在房间的角落里，角落在左边。

示例 2：

输入：n = 4
输出：3
解释：上图是四个盒子的放置方式。
这些盒子放在房间的角落里，角落在左边。

示例 3：

输入：n = 10
输出：6
解释：上图是十个盒子的放置方式。
这些盒子放在房间的角落里，角落在后面。

约束条件：

  • 1 <= n <= 10^9

解题思路

这道题目的关键在于理解如何在给定地板盒子数量的情况下，最大化可以放置的总盒子数。

首先分析盒子的放置规律：

  1. 为了支撑上层盒子，底层盒子必须形成一个"金字塔"结构，从角落开始逐层扩展
  2. 如果地板上有 m 个盒子，最优排列是形成一个三角形区域，从 (1,1) 开始，逐层向外扩展
  3. 第 i 层（从1开始）包含 i 个盒子排成一行，总共可以放置的盒子数为三角锥数

关键观察：

  • 当地板形成边长为 k 的三角形时（即前 k 层），总盒子数为 k*(k+1)*(k+2)/6
  • 如果需要更多盒子，可以在第 k+1 层添加部分盒子

算法思路：

  1. 使用二分查找或数学方法找到最大的完整三角锥层数 k，使得三角锥总数不超过 n
  2. 计算剩余需要放置的盒子数
  3. 在第 k+1 层逐个添加盒子，每添加一个地板盒子，可以支撑的总盒子数会增加相应的高度

具体实现时，我们可以先找到能放置的最大完整金字塔，然后计算还需要多少个额外的地板盒子来达到目标。

代码实现

class Solution {
public:
    int minimumBoxes(int n) {
        // 找到最大的完整三角锥
        long long k = 1;
        while (k * (k + 1) * (k + 2) / 6 <= n) {
            k++;
        }
        k--;
        
        // 完整三角锥的盒子数和底面盒子数
        long long totalBoxes = k * (k + 1) * (k + 2) / 6;
        long long baseBoxes = k * (k + 1) / 2;
        
        // 如果正好等于n，返回底面盒子数
        if (totalBoxes == n) {
            return baseBoxes;
        }
        
        // 还需要放置的盒子数
        long long remaining = n - totalBoxes;
        
        // 在下一层添加盒子
        long long additionalBase = 0;
        long long height = 1;
        
        while (remaining > 0) {
            additionalBase++;
            remaining -= height;
            if (remaining > 0) {
                height++;
            }
        }
        
        return baseBoxes + additionalBase;
    }
};

class Solution:
    def minimumBoxes(self, n: int) -> int:
        # 找到最大的完整三角锥
        k = 1
        while k * (k + 1) * (k + 2) // 6 <= n:
            k += 1
        k -= 1
        
        # 完整三角锥的盒子数和底面盒子数
        total_boxes = k * (k + 1) * (k + 2) // 6
        base_boxes = k * (k + 1) // 2
        
        # 如果正好等于n，返回底面盒子数
        if total_boxes == n:
            return base_boxes
        
        # 还需要放置的盒子数
        remaining = n - total_boxes
        
        # 在下一层添加盒子
        additional_base = 0
        height = 1
        
        while remaining > 0:
            additional_base += 1
            remaining -= height
            if remaining > 0:
                height += 1
        
        return base_boxes + additional_base

public class Solution {
    public int MinimumBoxes(int n) {
        // 找到最大的完整三角锥
        long k = 1;
        while (k * (k + 1) * (k + 2) / 6 <= n) {
            k++;
        }
        k--;
        
        // 完整三角锥的盒子数和底面盒子数
        long totalBoxes = k * (k + 1) * (k + 2) / 6;
        long baseBoxes = k * (k + 1) / 2;
        
        // 如果正好等于n，返回底面盒子数
        if (totalBoxes == n) {
            return (int)baseBoxes;
        }
        
        // 还需要放置的盒子数
        long remaining = n - totalBoxes;
        
        // 在下一层添加盒子
        long additionalBase = 0;
        long height = 1;
        
        while (remaining > 0) {
            additionalBase++;
            remaining -= height;
            if (remaining > 0) {
                height++;
            }
        }
        
        return (int)(baseBoxes + additionalBase);
    }
}

var minimumBoxes = function(n) {
    if (n <= 3) return n;
    
    // Find the largest tetrahedron that fits
    let k = 1;
    while (k * (k + 1) * (k + 2) / 6 <= n) {
        k++;
    }
    k--;
    
    let tetrahedron = k * (k + 1) * (k + 2) / 6;
    let remaining = n - tetrahedron;
    
    if (remaining === 0) {
        return k * (k + 1) / 2;
    }
    
    // Find how many additional boxes we need on the floor
    let j = 1;
    while (j * (j + 1) / 2 < remaining) {
        j++;
    }
    
    return k * (k + 1) / 2 + j;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(∛n)，主要是寻找最大完整三角锥的时间
空间复杂度O(1)，只使用常数额外空间

相关题目