Leetcode 1144:递减元素使数组呈锯齿状(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1144:递减元素使数组呈锯齿状(超详细的解法!!!)

in leetcode with 0 comment

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

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

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

示例 1:

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

示例 2:

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

提示:

解题思路

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

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 3
3 2 1
1 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://leetcode.com/problems/decrease-elements-to-make-array-zigzag/discuss/350576/JavaC%2B%2BPython-Easy-and-concise

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

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses