leetcode
leetcode 1601 ~ 1650
最少操作使数组递增

最少操作使数组递增

难度:

标签:

题目描述

代码结果

运行时间: 29 ms, 内存: 16.6 MB


/*
 * 思路:
 * 1. 使用Java Stream API来处理数组元素的增量操作。
 * 2. 初始化一个数组操作次数count为0,并将其包装为一个数组,以便在lambda表达式中进行修改。
 * 3. 使用IntStream来遍历数组元素,跳过第一个元素。
 * 4. 检查当前元素是否小于等于前一个元素,如果是,则计算需要增加的值并累加到count。
 * 5. 更新当前元素为前一个元素+1。
 * 6. 返回count的值。
 */

import java.util.stream.IntStream;

public class StrictlyIncreasingArrayStream {
    public int minOperations(int[] nums) {
        int[] count = {0};
        IntStream.range(1, nums.length).forEach(i -> {
            if (nums[i] <= nums[i - 1]) {
                count[0] += (nums[i - 1] - nums[i] + 1);
                nums[i] = nums[i - 1] + 1;
            }
        });
        return count[0];
    }

    public static void main(String[] args) {
        StrictlyIncreasingArrayStream solution = new StrictlyIncreasingArrayStream();
        int[] nums1 = {1, 1, 1};
        System.out.println(solution.minOperations(nums1)); // 输出: 3
        int[] nums2 = {1, 5, 2, 4, 1};
        System.out.println(solution.minOperations(nums2)); // 输出: 14
        int[] nums3 = {8};
        System.out.println(solution.minOperations(nums3)); // 输出: 0
    }
}

解释

方法:

本题解采用一种贪心算法的思路。从数组的第二个元素开始遍历,对于每个元素,检查它是否大于前一个元素。如果不是,则需要将其增加到比前一个元素大1的值,同时累加所需的操作次数。通过逐个调整,确保数组的每个后续元素都比前一个大,从而使数组严格递增。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
你如何确定使用贪心算法是解决这个问题的最佳方法?
贪心算法在此问题中适用,因为每一步调整只需要考虑前一个元素和当前元素,确保当前元素比前一个元素大即可。这种策略简单并且有效地逐步构建最终的递增序列。每次局部调整都是最优的,因为任何较小的增量不足以使当前元素成为递增序列的一部分,而任何较大的增量则可能导致更多的总操作次数。因此,逐步确保局部递增已经能够保证全局最优,这是贪心算法的核心特征。
🦆
在实现中,如果遇到连续多个相同的数字,这种情况下贪心算法的效率如何?
在遇到连续多个相同数字的情况下,贪心算法仍然有效,但操作次数可能会增加。例如,数组[5, 5, 5]需要进行调整为[5, 6, 7],每次都将后一个数字增加1以保持递增。这种情况下,每个需要增加的步骤都是必要的,因为没有其他方式可以用更少的总操作次数达到每个元素递增的要求。尽管操作次数增加,但贪心算法的时间效率仍然是线性的,即O(n),其中n是数组的长度。
🦆
为什么在算法中直接修改输入数组 `nums` 的值,这样做有什么特别的考虑吗?
在算法中直接修改输入数组 `nums` 的值主要是为了简化问题的处理过程和减少额外的空间使用。通过直接更新数组中的元素,可以避免使用额外的空间来存储调整后的值,从而使空间复杂度保持为O(1)。此外,这样做还可以直观地跟踪每个元素的变化,便于调试和验证算法的正确性。
🦆
代码中对于变量 `newNum` 的计算直接采用了 `prev + 1`,这里能否有其他选择以减少操作次数?
代码中使用 `prev + 1` 是为了确保当前元素比前一个元素大1,从而形成严格递增的序列。在这个特定问题中,选择 `prev + 1` 是最合适的,因为任何小于 `prev + 1` 的值都无法保证元素递增,而大于 `prev + 1` 的值虽然可以维持递增,但会导致更多的操作次数。因此,`prev + 1` 是既满足问题要求又确保操作次数最小的最佳选择。

相关问题