本文共 1681 字，大约阅读时间需要 5 分钟。

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

• 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
• 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

示例 1：

输入：nums = [1,2,3]输出：2解释：我们可以把 2 递减到 0，或把 3 递减到 1。

示例 2：

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

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

解题思路

这个问题首先不难想到暴力解法，也就是将两种情况模拟一遍取最小值即可

class Solution:    def movesToMakeZigzag(self, nums: List[int]) -> int:        def helper(data, f):            res = 0            for i in range(len(data)-1):                pre, cur = i, i + 1                if (f and data[pre] >= data[cur]) or (not f and data[pre] <= data[cur]):                    if f and data[pre] >= data[cur]:                        res += data[pre] - data[cur] + 1                        data[pre] = data[cur] - 1                    else:                        res += data[cur] - data[pre] + 1                        data[cur] = data[pre] - 1                f = not f            return res        return min(helper(nums[:], True), helper(nums[:], False))

这个问题有一个巧妙的思路。我们首先看这样的例子

1 2 33 2 11 3 2

对于上面三组数我们想让波峰变成波谷需要怎么做？只需要将中间的数变成min(l, r)-1即可，因为这样操作的次数最小。如果给定的数组就是波谷呢？我们可以这样处理max(0, mid - min(l, r) + 1)就可以得到最小操作次数。那么当我们考虑第一种情况的时候，我们只需要将所有偶数位置变成波谷即可。对于第二种情况实际上就是波谷变成波峰的问题，我们采用相同的思考方式，并且我们可以这个问题看成是将所有奇数位置变成波谷的问题。此时的问题就非常简单了，^_

class Solution:    def movesToMakeZigzag(self, nums: List[int]) -> int:        nums = [float("inf")] + nums + [float("inf")]        res = [0, 0]        for i in range(1, len(nums) - 1):            res[i % 2] += max(0, nums[i] - min(nums[i - 1], nums[i + 1]) + 1)        return min(res)

reference:

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/98478325 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！