递减元素使数组呈锯齿状【LC1144】
给你一个整数数组
nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。如果符合下列情况之一，则数组
A就是 锯齿数组：
- 每个偶数索引对应的元素都大于相邻的元素，即
A[0] > A[1] < A[2] > A[3] < A[4] > ...- 或者，每个奇数索引对应的元素都大于相邻的元素，即
A[0] < A[1] > A[2] < A[3] > A[4] < ...
返回将数组 nums 转换为锯齿数组所需的最小操作次数。
- 思路：贪心+枚举
实现
class Solution { public int movesToMakeZigzag(int[] nums) { int a = 0, b = 0; int n = nums.length; if (n == 1) return 0; for (int i = 0; i < n; i++){ int count = 0; if (i - 1 >= 0){ count = Math.max(nums[i] - nums[i - 1] + 1, count); } if (i + 1 < n){ count = Math.max(nums[i] - nums[i + 1] + 1, count); } if ((i & 1 )== 0){// 偶数 a += count; }else{// 奇数 b += count; } } return Math.min(a, b); } }
复杂度
- 时间复杂度：O ( n )
空间复杂度：O ( 1 )
