【2022-12-25每日一题】1739. 放置盒子[Hard]
2022-12-25
1分钟阅读时长
2022-12-25每日一题：1739. 放置盒子
难度：Hard
标签：贪心 、 数学 、 二分查找
有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：
- 你可以把盒子放在地板上的任何地方。
- 如果盒子
x需要放置在盒子y的顶部，那么盒子y竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。
示例 1：
输入：n = 3 输出：3 解释：上图是 3 个盒子的摆放位置。 这些盒子放在房间的一角，对应左侧位置。
示例 2：
输入：n = 4 输出：3 解释：上图是 3 个盒子的摆放位置。 这些盒子放在房间的一角，对应左侧位置。
示例 3：
输入：n = 10 输出：6 解释：上图是 10 个盒子的摆放位置。 这些盒子放在房间的一角，对应后方位置。
提示：
1 <= n <= 109
方法一：ylb
func minimumBoxes(n int) int {
s, k := 0, 1
for s+k*(k+1)/2 <= n {
s += k*(k+1)/2
k++
}
k--
ans := k*(k+1)/2
for s < n {
ans++
s += k
k++
}
return ans
}
复杂度分析
- 时间复杂度: $O(\sqrt{n})$，空间复杂度 $O(1)$。其中 n 为题目给定的盒子数量。
方法二：灵茶山艾府
func minimumBoxes(n int) (ans int) {
maxN := 0
for i := 1; maxN + ans+i <= n; i++ {
ans += i
maxN += ans
}
for j := 1; maxN < n; j++ {
ans++
maxN += j
}
return ans
}
方法三：力扣官方
func minimumBoxes(n int) int {
cur, i, j := 1, 1, 1
for n > cur {
n -= cur
i++
cur += i
}
cur = 1
for n > cur {
n -= cur
j++
cur++
}
return (i-1)*i/2 + j
}