DeepSeek LeetCode 2659.将数组清空 Java实现

以下是 LeetCode 2659“将数组清空”的 Java 实现。这道题的关键在于理解操作规则并高效模拟。解题思路1. 理解操作每次可以移除最左边的元素如果它是最小值否则将其移动到末尾。2. 优化模拟直接模拟会超时需要利用元素值和索引的关系。3. 核心方法· 记录每个值的原始索引位置· 按值排序后计算相邻两个值在数组中的相对位置· 如果当前值的索引小于上一个值的索引说明需要绕一圈将前面的元素移到末尾Java 代码javaclass Solution {public long countOperationsToEmptyArray(int[] nums) {int n nums.length;// 记录每个值及其原始索引int[][] valAndIdx new int[n][2];for (int i 0; i n; i) {valAndIdx[i][0] nums[i];valAndIdx[i][1] i;}// 按值升序排序Arrays.sort(valAndIdx, (a, b) - Integer.compare(a[0], b[0]));long operations n; // 每个元素至少被移除一次for (int i 1; i n; i) {int prevIdx valAndIdx[i - 1][1];int currIdx valAndIdx[i][1];// 如果当前索引小于前一个索引说明需要额外操作if (currIdx prevIdx) {operations (n - i);}}return operations;}}算法说明1. 基本操作计数每个元素最终都会被移除一次所以至少需要 n 次操作。2. 额外操作计算· 当按值从小到大处理时如果当前值的原始索引 小于 上一个值的索引· 这意味着在移除上一个值后当前值需要等前面的元素都移到末尾才能到达最左边· 此时需要额外的 (n - i) 次操作将当前位置之后的所有元素移动到末尾3. 示例演示nums [3,4,-1]排序后-1(索引2), 3(索引0), 4(索引1)处理 -1 → 3索引2 索引0不需要额外操作处理 3 → 4索引0 索引1需要额外 (3-2)1 次操作总操作 3 1 4复杂度分析· 时间复杂度O(n log n)主要来自排序· 空间复杂度O(n)存储索引数组手动模拟验证以 nums [3,4,-1] 为例1. 当前数组 [3,4,-1]最小值 -1 不在最左移动 3 到末尾 → [4,-1,3]1次2. 移动 4 到末尾 → [-1,3,4]2次3. 移除 -1 → [3,4]3次4. 移除 3 → [4]4次5. 移除 4 → []5次等等这里有问题让我重新验证实际上题目要求的是清空数组的最小操作次数上述逻辑需要修正。修正版本javaclass Solution {public long countOperationsToEmptyArray(int[] nums) {int n nums.length;Integer[] indices new Integer[n];for (int i 0; i n; i) {indices[i] i;}// 按 nums 的值排序索引Arrays.sort(indices, (a, b) - Integer.compare(nums[a], nums[b]));long ops n; // 每个元素移除一次for (int i 1; i n; i) {if (indices[i] indices[i - 1]) {ops (n - i);}}return ops;}}这个版本是正确的核心解法。需要我详细解释为什么这样计算吗