leetcode
leetcode 1051 ~ 1100
递减元素使数组呈锯齿状

递减元素使数组呈锯齿状

难度:

标签:

题目描述

代码结果

运行时间: 30 ms, 内存: 16.0 MB


/*
 * 思路:使用Java Stream API,我们仍然需要分别检查两种锯齿数组情况。
 * 我们可以通过Stream的过滤和映射操作来简化操作次数的计算。
 */
import java.util.stream.IntStream;

public class Solution {
    public int movesToMakeZigzag(int[] nums) {
        return Math.min(
            helper(nums, 0),
            helper(nums, 1)
        );
    }

    private int helper(int[] nums, int index) {
        return IntStream.range(0, nums.length)
            .filter(i -> i % 2 == index)
            .map(i -> {
                int left = (i > 0) ? nums[i - 1] : Integer.MAX_VALUE;
                int right = (i < nums.length - 1) ? nums[i + 1] : Integer.MAX_VALUE;
                int decreaseTo = Math.min(left, right) - 1;
                return nums[i] >= decreaseTo ? nums[i] - decreaseTo : 0;
            })
            .sum();
    }
}

解释

方法:

该题解采用了直观的遍历方法来解决问题。为了使数组成为锯齿形数组,我们考虑两种可能的锯齿模式:1) 偶数索引的元素大于其相邻的元素;2) 奇数索引的元素大于其相邻的元素。对于每个元素,我们计算将其减少到比相邻元素小的最小操作次数,以满足当前考虑的锯齿模式。然后,对于两种模式,我们各自维护一个操作次数累计器,最后返回两种模式中需要的最小操作次数。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算减少次数时,使用的是`nums[i] - min(left, right) + 1`而不是直接`nums[i] - min(left, right)`?
这种计算方式是为了确保当前索引处的元素严格大于其相邻的元素。如果使用`nums[i] - min(left, right)`,则只能保证`nums[i]`等于较小的相邻元素,但不一定大于它。通过增加1,我们确保`nums[i]`大于左右两边的较小值,从而满足锯齿形数组的条件。
🦆
在处理数组边界时,为什么选择将不存在的相邻元素值设置为无穷大`float('inf')`?
将不存在的相邻元素值设置为无穷大是为了简化边界条件的处理。这样做确保任何实际存在的元素都不会大于`float('inf')`,因此在边界处的元素不需要进行任何减少操作来保证比不存在的相邻元素大。这种处理方式允许我们使用统一的逻辑来处理数组中所有元素的条件判断。
🦆
如果数组长度为奇数或偶数,这对计算最小操作次数有什么具体影响吗?
数组的长度(奇数或偶数)直接影响每种锯齿模式中涉及的元素数量。例如,如果数组长度是奇数,那么在模式1(偶数索引的元素大于相邻元素)中,偶数索引的数量将多于奇数索引的模式2。这可能导致需要在某一模式中进行更多的调整。因此,数组的长度会影响两种模式的操作次数,从而可能影响哪一种模式具有更小的操作次数。
🦆
为什么选择比较两种锯齿模式的操作次数,而不是在遍历过程中直接调整元素到最终状态?
选择比较两种锯齿模式的操作次数而不是直接调整元素,是因为在处理开始时不确定哪种模式将导致最小的总操作次数。直接调整元素可能会导致选择了次优的锯齿模式,从而增加不必要的操作次数。通过计算两种模式的操作次数,可以确保选择更优化的解决方案,因为我们有机会比较哪一种模式在总体上更有效。

相关问题