What is the optimal approach for the "Make Array Empty" problem?

The optimal approach involves using binary search over the possible answer space and applying greedy strategies for efficient element removal.

How does binary search apply to this problem?

Binary search helps minimize the number of operations by narrowing down the valid answer space, effectively reducing the time complexity.

What are the common pitfalls in solving the "Make Array Empty" problem?

Common pitfalls include misunderstanding the operation order, using unnecessary data structures, or not efficiently handling the array removal process.

What data structures can help solve this problem more efficiently?

Segment trees and binary indexed trees are helpful for efficiently querying and updating the state of the array during element removal.

Can this problem be solved without binary search?

While binary search is the most efficient approach, the problem can be solved with other strategies, though they may be less optimized.

#2659

Hard

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

LeetCode 题解工作台

将数组清空

给你一个包含若干互不相同整数的数组 nums ，你需要执行以下操作直到数组为空：如果数组中第一个元素是当前数组中的最小值，则删除它。否则，将第一个元素移动到数组的末尾。请你返回需要多少个操作使 nums 为空。示例 1：输入： nums = [3,4,-1] 输出： 5 …

数组二分查找贪心树状数组线段树

题目描述

给你一个包含若干 互不相同 整数的数组 nums ，你需要执行以下操作直到数组为空 ：

如果数组中第一个元素是当前数组中的 最小值 ，则删除它。
否则，将第一个元素移动到数组的末尾。

请你返回需要多少个操作使 nums 为空。

示例 1：

输入：nums = [3,4,-1]
输出：5

Operation	Array
1	[4, -1, 3]
2	[-1, 3, 4]
3	[3, 4]
4	[4]
5	[]

示例 2：

输入：nums = [1,2,4,3]
输出：5

Operation	Array
1	[2, 4, 3]
2	[4, 3]
3	[3, 4]
4	[4]
5	[]

示例 3：

输入：nums = [1,2,3]
输出：3

Operation	Array
1	[2, 3]
2	[3]
3	[]

提示：

1 <= nums.length <= 10⁵
-10⁹<= nums[i] <= 10⁹
nums 中的元素 互不相同 。

lightbulb

解题思路

方法一：哈希表 + 排序 + 树状数组

我们先用哈希表 $pos$ 记录数组 $nums$ 中每个元素的位置，接下来对数组 $nums$ 进行排序，那么数组最小值的下标为 $pos[nums[0]]$ ，移动到数组的第一个位置并且删除，需要 $pos[nums[0]] + 1$ 次操作，因此初始答案为 $ans = pos[nums[0]] + 1$ 。

接下来，我们遍历排序后的数组 $nums$ ，相邻两个元素 $a$ 和 $b$ 的下标分别为 $i=pos[a]$ , $j=pos[b]$ 。那么将第二个元素 $b$ 移动到数组第一个位置并且删除所需要的操作数，等于两个下标的间隔，减去两个下标之间此前删除的下标个数，累加操作数到答案中。我们可以用树状数组或者有序列表维护已删除的下标，这样就可以在 $O(\log n)$ 的时间内求出两个下标之间已删除的下标个数。注意，如果 $i \gt j$ ，那么需要额外增加 $n - k$ 次操作，其中 $k$ 是当前遍历到的位置。

遍历结束后，返回操作数 $ans$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        pos = {x: i for i, x in enumerate(nums)}
        nums.sort()
        sl = SortedList()
        ans = pos[nums[0]] + 1
        n = len(nums)
        for k, (a, b) in enumerate(pairwise(nums)):
            i, j = pos[a], pos[b]
            d = j - i - sl.bisect(j) + sl.bisect(i)
            ans += d + (n - k) * int(i > j)
            sl.add(i)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate understanding of binary search over a valid answer space.
question_mark
Look for clear reasoning in how the greedy approach is applied to the problem.
question_mark
Evaluate if the candidate considers advanced data structures like segment trees or binary indexed trees for optimization.

warning

常见陷阱

外企场景

error
Misunderstanding the order of operations and how it affects the number of steps needed.
error
Overcomplicating the problem by applying unnecessary data structures when binary search is sufficient.
error
Failure to recognize the importance of efficiently querying and updating the array's state during removal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing a variation with different array constraints, such as non-distinct values.
arrow_right_alt
Modifying the problem to remove elements based on a different criterion, like value-based removal rather than order.
arrow_right_alt
Introducing multiple arrays and determining the combined minimum number of operations across all arrays.

help

常见问题

外企场景

继续练习

#2736 最大和查询 #2426 满足不等式的数对数目 #2179 统计数组中好三元组数目