JZX轻语：简

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

发表于2024年06月24日

一开始想复杂了，其实只能递减元素。分情况讨论即可：对于arr[0] < arr[1] > arr[2] < ...这种情况，只能递减arr[1], arr[3], arr[2k + 1]，每个元素的只需要递减到两侧元素最小者 - 1即可，累加这些元素的最少递减次数；对于另一种情况，继续上文的步骤，最后取两种情况的最小值即可。

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        ans1 = 0
        for i in range(1, len(nums), 2):
            # 对于边界取值, 直接取1001即可, 题目条件中最大值为1000
            target = min(nums[i - 1], nums[i + 1] if i + 1 < len(nums) else 1001) - 1
            ans1 += max(0, nums[i] - target)
        ans2 = 0
        for i in range(0, len(nums), 2):
            target = min(nums[i - 1] if i > 0 else 1001, nums[i + 1] if i + 1 < len(nums) else 1001) - 1
            ans2 += max(0, nums[i] - target)
        return min(ans1, ans2)

闪念标签：LC

题目链接：https://leetcode.cn/problems/decrease-elements-to-make-array-zigzag/