1144. 递减元素使数组呈锯齿状

ITCharge大约 4 分钟

---

1144. 递减元素使数组呈锯齿状

标签：贪心、数组
难度：中等

题目链接

1144. 递减元素使数组呈锯齿状 - 力扣

题目大意

描述：给定一个整数数组 $nums$ ，每次操作可以把其中任意一个元素的值减 1。

锯齿数组：一个数组如果像锯齿一样「高低高」或「低高低」交替，就叫锯齿数组。具体有两种形态：

形态 A：偶数位置的值 > 相邻的奇数位置的值（高—低—高—低…）。
即 $nums[0] > nums[1] < nums[2] > nums[3] < nums[4] > ...$
形态 B：奇数位置的值 > 相邻的偶数位置的值（低—高—低—高…）。
即 $nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < ...$

要求：只能做「减 1」操作，不能增加数字。返回把数组变成锯齿数组所需的最少操作次数。

说明：

$1 \le nums.length \le 10^{3}$ 。
$1 \le nums[i] \le 10^{3}$ 。

示例：

示例 1：

输入：nums = [1,2,3]
输出：2
解释：可以减 2（1 次操作）或减 3（2 次操作），最少 2 次。

示例 2：

输入：nums = [9,6,1,6,2]
输出：4

解题思路

思路 1：贪心

这道题的突破口在于：只有当「波谷」位置（即应该较小的位置）比它两边的波峰都大时，才需要减少它的值。

因为只能做减 1 操作，不能加 1，所以我们的策略是：减少波谷位置的值，让它小于两边的波峰。

两种形态都要考虑：

形态 A（偶数位置是波峰）：下标 0、2、4… 是大的（波峰），下标 1、3、5… 是小的（波谷）。所以我们只需要减少奇数位置的值，让它们小于左右邻居。
形态 B（奇数位置是波峰）：下标 1、3、5… 是大的（波峰），下标 0、2、4… 是小的（波谷）。所以我们只需要减少偶数位置的值，让它们小于左右邻居。

对于每个波谷位置 $i$ ，需要减到多少？

它必须比左右两边相邻的元素都小。所以它最终的值最多是 $\min(左边邻居, 右边邻居) - 1$ 。如果它当前的值已经小于这个值了，就不用减了；否则需要减少：当前值 - 目标值。

为什么只减波谷不减波峰？
因为只能做减法。如果波峰太矮，我们没法把它加高，只能把旁边的波谷降得更低。所以我们只需要调整波谷。

步骤拆解：

准备两个变量，分别记录两种形态需要操作的次数。
遍历数组的每个位置：
- 找到左右邻居的值（越界的视为无限大）。
- 计算 $\min(左邻居, 右邻居)$ 。
- 如果当前值 >= 这个最小值，就需要减少到 $\min(左邻居, 右邻居) - 1$ ，操作次数 = 当前值 - 目标值。
- 把这个操作次数累加到对应形态的结果上。
最后取两个结果中的较小值。

思路 1：代码

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        
        # res[0] 记录形态 A（偶数位是波峰，减少奇数位）的操作次数
        # res[1] 记录形态 B（奇数位是波峰，减少偶数位）的操作次数
        res = [0, 0]
        
        for i in range(n):
            # 取左右邻居中的最小值（越界时当作无限大，不需要比较）
            left = nums[i - 1] if i > 0 else float('inf')
            right = nums[i + 1] if i < n - 1 else float('inf')
            min_neighbor = min(left, right)
            
            # 如果当前值 >= 相邻最小值，就需要减少它
            if nums[i] >= min_neighbor:
                # res[0] 对应偶数位置是波峰（i%2==0 是波谷位置）
                # res[1] 对应奇数位置是波峰（i%2==1 是波谷位置）
                res[i % 2] += nums[i] - min_neighbor + 1
        
        # 返回两种形态中操作次数更少的那个
        return min(res)

思路 1：复杂度分析

时间复杂度： $O(n)$ 。用人话说就是：从头到尾遍历一次数组就够了， $n$ 是数组长度。
空间复杂度： $O(1)$ 。只用了几个固定变量。