Hard

题目描述

给你一个包含不同数字的整数数组 nums，你可以执行以下操作直到数组为空：

  • 如果第一个元素是最小值，则将其移除
  • 否则，将第一个元素移到数组末尾

返回一个整数，表示使 nums 变为空数组所需的操作次数。

示例 1:

输入：nums = [3,4,-1]
输出：5
解释：
操作 1: [4, -1, 3]
操作 2: [-1, 3, 4]  
操作 3: [3, 4]
操作 4: [4]
操作 5: []

示例 2:

输入：nums = [1,2,4,3]
输出：5
解释：
操作 1: [2, 4, 3]
操作 2: [4, 3]
操作 3: [3, 4]
操作 4: [4]
操作 5: []

示例 3:

输入：nums = [1,2,3]
输出：3
解释：
操作 1: [2, 3]
操作 2: [3]
操作 3: []

提示：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums 中的所有值都不相同

解题思路

这道题的关键是理解元素的移除顺序：我们必须按照从小到大的顺序移除元素。

思路分析：

  1. 核心观察：元素必须按值的升序被移除。每次只能移除当前位于数组开头的最小元素。

  2. 模拟过程：

    • 将数组按值排序，得到移除顺序
    • 对于每个要移除的元素，计算需要多少次操作才能将其移动到数组开头
    • 关键是计算当前元素前面还有多少个未被移除的元素

  3. 优化方法：

    • 使用索引映射记录每个值在原数组中的位置
    • 按值排序后，依次处理每个元素
    • 使用数据结构（如树状数组或有序集合）快速计算当前位置前面剩余元素的数量

  4. 计算公式：

    • 对于每个元素，操作数 = 当前位置前面剩余元素数量 + 1（移除操作）
    • 需要考虑数组的循环特性：如果当前元素位置小于上一个被移除元素的位置，说明发生了"绕一圈"

推荐解法：使用有序集合（TreeSet/SortedList）来维护剩余元素的索引，可以高效地查询和删除。

代码实现

class Solution {
public:
    long long countOperationsToEmptyArray(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int, int>> sorted_nums;
        
        for (int i = 0; i < n; i++) {
            sorted_nums.push_back({nums[i], i});
        }
        sort(sorted_nums.begin(), sorted_nums.end());
        
        set<int> remaining_indices;
        for (int i = 0; i < n; i++) {
            remaining_indices.insert(i);
        }
        
        long long operations = 0;
        int last_pos = 0;
        
        for (auto& [val, idx] : sorted_nums) {
            auto it = remaining_indices.find(idx);
            int current_pos = distance(remaining_indices.begin(), it);
            
            if (current_pos >= last_pos) {
                operations += current_pos - last_pos + 1;
            } else {
                operations += remaining_indices.size() - last_pos + current_pos + 1;
            }
            
            last_pos = current_pos;
            remaining_indices.erase(it);
        }
        
        return operations;
    }
};

class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        n = len(nums)
        sorted_nums = sorted((val, idx) for idx, val in enumerate(nums))
        
        from sortedcontainers import SortedList
        remaining_indices = SortedList(range(n))
        
        operations = 0
        last_pos = 0
        
        for val, idx in sorted_nums:
            current_pos = remaining_indices.index(idx)
            
            if current_pos >= last_pos:
                operations += current_pos - last_pos + 1
            else:
                operations += len(remaining_indices) - last_pos + current_pos + 1
            
            last_pos = current_pos
            remaining_indices.remove(idx)
        
        return operations

public class Solution {
    public long CountOperationsToEmptyArray(int[] nums) {
        int n = nums.Length;
        var sortedNums = nums.Select((val, idx) => new { Value = val, Index = idx })
                            .OrderBy(x => x.Value)
                            .ToList();
        
        var remainingIndices = new SortedSet<int>();
        for (int i = 0; i < n; i++) {
            remainingIndices.Add(i);
        }
        
        long operations = 0;
        int lastPos = 0;
        
        foreach (var item in sortedNums) {
            var remainingList = remainingIndices.ToList();
            int currentPos = remainingList.IndexOf(item.Index);
            
            if (currentPos >= lastPos) {
                operations += currentPos - lastPos + 1;
            } else {
                operations += remainingIndices.Count - lastPos + currentPos + 1;
            }
            
            lastPos = currentPos;
            remainingIndices.Remove(item.Index);
        }
        
        return operations;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countOperationsToEmptyArray = function(nums) {
    const n = nums.length;
    const sortedNums = nums.map((val, idx) => [val, idx]).sort((a, b) => a[0] - b[0]);
    
    const remainingIndices = new Set();
    for (let i = 0; i < n; i++) {
        remainingIndices.add(i);
    }
    
    let operations = 0;
    let lastPos = 0;
    
    for (const [val, idx] of sortedNums) {
        const remainingArray = Array.from(remainingIndices).sort((a, b) => a - b);
        const currentPos = remainingArray.indexOf(idx);
        
        if (currentPos >= lastPos) {
            operations += currentPos - lastPos + 1;
        } else {
            operations += remainingIndices.size - lastPos + currentPos + 1;
        }
        
        lastPos = currentPos;
        remainingIndices.delete(idx);
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大O表示法说明
时间复杂度O(n log n)排序需要O(n log n)，每次查找和删除操作需要O(log n)
空间复杂度O(n)需要额外的数据结构存储排序后的数组和剩余索引