题目链接：1144. 递减元素使数组呈锯齿状
方法：找规律 + 模拟
解题思路
对于一个整数数组 \(nums\)，可以转换为题目中两种锯齿数组，对于两种情况的转换取最小值。
并且由于操作只能将一个元素减1，因此：
- 对于第1种情况，只用下标为奇数的元素需要减小到比两边最小值小1；
- 对于第2种情况，只用下标为偶数的元素减小到比两边最小值小1。
代码
class Solution {
public:
int movesToMakeZigzag(vector<int>& nums) {
int cnt1 = 0, cnt2 = 0;
int n = nums.size();
for (int i = 0; i < n; i ++ ) {
int mi = 1001;
if (i - 1 >= 0) mi = min(mi, nums[i - 1]);
if (i + 1 < n) mi = min(mi, nums[i + 1]);
if (nums[i] >= mi && i % 2 != 0) cnt1 += nums[i] - mi + 1;
if (nums[i] >= mi && i % 2 == 0) cnt2 += nums[i] - mi + 1;
}
return min(cnt1, cnt2);
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。