难度: Medium
给你一个整数数组 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 <= 10001 <= nums[i] <= 1000运行时间: 30 ms
内存: 16.0 MB
class Solution:
def movesToMakeZigzag(self, nums: List[int]) -> int:
n = len(nums)
# 初始化两种情况下的操作次数
count1, count2 = 0, 0
for i in range(n):
# 对于情况1：偶数索引的元素大于相邻元素
if i % 2 == 0:
left = nums[i - 1] if i > 0 else float('inf')
right = nums[i + 1] if i < n - 1 else float('inf')
count1 += max(0, nums[i] - min(left, right) + 1)
# 对于情况2：奇数索引的元素大于相邻元素
else:
left = nums[i - 1] if i > 0 else float('inf')
right = nums[i + 1] if i < n - 1 else float('inf')
count2 += max(0, nums[i] - min(left, right) + 1)
# 返回两种情况下的最小操作次数
return min(count1, count2)
该题解采用了直观的遍历方法来解决问题。为了使数组成为锯齿形数组，我们考虑两种可能的锯齿模式：1) 偶数索引的元素大于其相邻的元素；2) 奇数索引的元素大于其相邻的元素。对于每个元素，我们计算将其减少到比相邻元素小的最小操作次数，以满足当前考虑的锯齿模式。然后，对于两种模式，我们各自维护一个操作次数累计器，最后返回两种模式中需要的最小操作次数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def movesToMakeZigzag(self, nums: List[int]) -> int:
n = len(nums)
# 初始化两种情况下的操作次数
count1, count2 = 0, 0
for i in range(n):
# 对于情况1：偶数索引的元素大于相邻元素
if i % 2 == 0:
left = nums[i - 1] if i > 0 else float('inf')
right = nums[i + 1] if i < n - 1 else float('inf')
# 计算当前元素应该减少的次数以确保大于左右相邻元素
count1 += max(0, nums[i] - min(left, right) + 1)
# 对于情况2：奇数索引的元素大于相邻元素
else:
left = nums[i - 1] if i > 0 else float('inf')
right = nums[i + 1] if i < n - 1 else float('inf')
# 计算当前元素应该减少的次数以确保大于左右相邻元素
count2 += max(0, nums[i] - min(left, right) + 1)
# 返回两种情况下的最小操作次数
return min(count1, count2)
这种计算方式是为了确保当前索引处的元素严格大于其相邻的元素。如果使用`nums[i] - min(left, right)`，则只能保证`nums[i]`等于较小的相邻元素，但不一定大于它。通过增加1，我们确保`nums[i]`大于左右两边的较小值，从而满足锯齿形数组的条件。
将不存在的相邻元素值设置为无穷大是为了简化边界条件的处理。这样做确保任何实际存在的元素都不会大于`float('inf')`，因此在边界处的元素不需要进行任何减少操作来保证比不存在的相邻元素大。这种处理方式允许我们使用统一的逻辑来处理数组中所有元素的条件判断。
数组的长度（奇数或偶数）直接影响每种锯齿模式中涉及的元素数量。例如，如果数组长度是奇数，那么在模式1（偶数索引的元素大于相邻元素）中，偶数索引的数量将多于奇数索引的模式2。这可能导致需要在某一模式中进行更多的调整。因此，数组的长度会影响两种模式的操作次数，从而可能影响哪一种模式具有更小的操作次数。
选择比较两种锯齿模式的操作次数而不是直接调整元素，是因为在处理开始时不确定哪种模式将导致最小的总操作次数。直接调整元素可能会导致选择了次优的锯齿模式，从而增加不必要的操作次数。通过计算两种模式的操作次数，可以确保选择更优化的解决方案，因为我们有机会比较哪一种模式在总体上更有效。