What is the best way to approach Minimum Number of Seconds to Make Mountain Height Zero?

Use binary search over the total time and verify feasibility with a greedy sum of worker contributions.

Can we solve this problem without binary search?

A naive simulation is possible but inefficient; binary search ensures optimal time complexity and handles large inputs.

How do workerTimes affect the solution?

Workers with smaller times can reduce more units per second, and the feasibility check must sum all contributions to meet mountainHeight.

What is a common mistake when implementing this solution?

Overlooking simultaneous work and summing contributions incorrectly can lead to wrong minimum seconds.

How does the binary search pattern apply here?

The pattern searches the smallest time where the combined work of all workers can reduce the mountainHeight to zero, efficiently narrowing the range.

#3296

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

移山所需的最少秒数

给你一个整数 mountainHeight 表示山的高度。同时给你一个整数数组 workerTimes ，表示工人们的工作时间（单位：秒）。工人们需要同时进行工作以降低山的高度。对于工人 i : 山的高度降低 x ，需要花费 workerTimes[i] + workerTimes[…

数组数学二分查找贪心堆（优先队列）

题目描述

给你一个整数 mountainHeight 表示山的高度。

同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。

工人们需要同时进行工作以降低山的高度。对于工人 i :

山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：
- 山的高度降低 1，需要 workerTimes[i] 秒。
- 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。

返回一个整数，表示工人们使山的高度降低到 0 所需的最少秒数。

示例 1：

输入： mountainHeight = 4, workerTimes = [2,1,1]

输出： 3

解释：

将山的高度降低到 0 的一种方式是：

工人 0 将高度降低 1，花费 workerTimes[0] = 2 秒。
工人 1 将高度降低 2，花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
工人 2 将高度降低 1，花费 workerTimes[2] = 1 秒。

因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。

示例 2：

输入： mountainHeight = 10, workerTimes = [3,2,2,4]

输出： 12

解释：

工人 0 将高度降低 2，花费 workerTimes[0] + workerTimes[0] * 2 = 9 秒。
工人 1 将高度降低 3，花费 workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 秒。
工人 2 将高度降低 3，花费 workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 秒。
工人 3 将高度降低 2，花费 workerTimes[3] + workerTimes[3] * 2 = 12 秒。

所需的最少时间为 max(9, 12, 12, 12) = 12 秒。

示例 3：

输入： mountainHeight = 5, workerTimes = [1]

输出： 15

解释：

这个示例中只有一个工人，所以答案是 workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15 秒。

提示：

1 <= mountainHeight <= 10⁵
1 <= workerTimes.length <= 10⁴
1 <= workerTimes[i] <= 10⁶

lightbulb

解题思路

方法一：二分查找

我们注意到，如果所有的工人能在 $t$ 秒内将山的高度降低到 $0$ ，那么对于任意 $t' > t$ ，工人们也能在 $t'$ 秒内将山的高度降低到 $0$ 。因此，我们可以使用二分查找的方法找到最小的 $t$ ，使得工人们能在 $t$ 秒内将山的高度降低到 $0$ 。

我们定义一个函数 $\textit{check}(t)$ ，表示工人们能否在 $t$ 秒内将山的高度降低到 $0$ 。具体地，我们遍历每一个工人，对于当前工人 $\textit{workerTimes}[i]$ ，假设他在 $t$ 秒内降低了 $h'$ 的高度，那么我们可以得到一个不等式：

\left(1 + h'\right) \cdot \frac{h'}{2} \cdot \textit{workerTimes}[i] \leq t

解不等式得到：

h' \leq \left\lfloor \sqrt{\frac{2t}{\textit{workerTimes}[i]} + \frac{1}{4}} - \frac{1}{2} \right\rfloor

我们可以将所有工人的 $h'$ 相加，得到总共降低的高度 $h$ ，如果 $h \geq \textit{mountainHeight}$ ，那么说明工人们能在 $t$ 秒内将山的高度降低到 $0$ 。

接下来，我们确定二分查找的左边界 $l = 1$ ，由于最少有一个工作，且每个工人的工作时间不超过 $10^6$ ，要想使山的高度降低到 $0$ ，最少需要 $(1 + \textit{mountainHeight}) \cdot \textit{mountainHeight} / 2 \cdot \textit{workerTimes}[i] \leq 10^{16}$ 秒，因此我们可以确定二分查找的右边界 $r = 10^{16}$ 。然后我们不断地将区间 $[l, r]$ 二分，直到 $l = r$ ，此时 $l$ 即为答案。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 为工人的数量，而 $M$ 为二分查找的右边界，本题中 $M = 10^{16}$ 。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        def check(t: int) -> bool:
            h = 0
            for wt in workerTimes:
                h += int(sqrt(2 * t / wt + 1 / 4) - 1 / 2)
            return h >= mountainHeight

        return bisect_left(range(10**16), True, key=check)

speed

复杂度分析

指标	值
时间	complexity is O(n * log(maxTime)) where n is the number of workers and maxTime is the upper bound for binary search. Space complexity is O(1) extra if calculations are done in-place, otherwise O(n) for storing contributions.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you thinking about iterating over all possible seconds or can we use a smarter approach?
question_mark
Consider how the workers' different times affect the total reduction and feasibility check.
question_mark
Can you implement a binary search over the valid answer space instead of naive simulation?

warning

常见陷阱

外企场景

error
Assuming sequential work instead of simultaneous worker contributions can overestimate time.
error
Neglecting to check if total units reduced in candidate time meets the mountainHeight.
error
Failing to set a sufficiently large upper bound for binary search may give incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of finding minimum seconds, compute the maximum mountainHeight that can be reduced in a fixed number of seconds.
arrow_right_alt
Consider a version where workers have cooldown periods between units of work.
arrow_right_alt
Modify the problem to include varying efficiencies depending on current mountainHeight levels.

help

常见问题

外企场景

继续练习

#3049 标记所有下标的最早秒数 II #3605 数组的最小稳定性因子 #2967 使数组成为等数数组的最小代价