1144. 递减元素使数组呈锯齿状

题目链接：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)\)。