1144. 递减元素使数组呈锯齿状（中等）- LeetCode

题目描述

自己解法

动态规划的思想，分别计算按奇、偶数索引形成锯齿需要的次数，在进行比较。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

class Solution:def movesToMakeZigzag(self, nums: List[int]) -> int:count_odd,count_even = 0,0temp_odd,temp_even = 0,0for i in range(1,len(nums)):if i % 2 == 0:## 奇数索引主导temp_odd = max(nums[i]-nums[i-1]+1,0)count_odd += temp_odd## 偶数索引主导count_even += max(nums[i-1]-nums[i]-temp_even+1,0)else:## 奇数索引主导count_odd += max(nums[i-1]-nums[i]-temp_odd+1,0)## 偶数索引主导temp_even = max(nums[i]-nums[i-1]+1,0)count_even += temp_evenreturn min(count_even,count_odd)