发表于 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 题目链接