🪑 1144.递减元素使数组呈锯齿状
给你一个整数数组 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
//分别计算奇数位置为波峰或者偶数位置为波峰谁的步数小即可
//也就是要统计两遍，然后比较
public int movesToMakeZigzag(int[] nums) {
int[] temp=Arrays.copyOf(nums,nums.length);
int odd=0,even=0;//分别代表奇数和偶数为波峰的情况下需要变化多少步
//奇数为波峰
for(int i=0;i<temp.length;i+=2){
if(i-1>=0&&temp[i]>=temp[i-1]){//左边
odd+=(temp[i]-temp[i-1]+1);
temp[i]=temp[i-1]-1;
}
if(i+1<temp.length&&temp[i]>=temp[i+1]){//右边
odd+=(temp[i]-temp[i+1]+1);
temp[i]=temp[i+1]-1;
}
}
//偶数为波峰
for(int i=1;i<nums.length;i+=2){
if(i-1>=0&&nums[i]>=nums[i-1]){//左边
even+=(nums[i]-nums[i-1]+1);
nums[i]=nums[i-1]-1;
}
if(i+1<nums.length&&nums[i]>=nums[i+1]){//右边
even+=(nums[i]-nums[i+1]+1);
nums[i]=nums[i+1]-1;
}
}
return Math.min(odd,even);
}
}
|
总结
要从问题中抓住核心，这道问题的核心就是谁当波峰，一旦有元素当波峰，那么相邻的元素必须不能比波峰高，相等都不行，为了求出最小的步数，不符合要求的元素在递减时递减到刚好小于即可