题目描述

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

• 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
• 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

样例

输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。

输入：nums = [9,6,1,6,2]
输出：4

限制

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

算法

(贪心) $O(n)$

1. 数组长度等于 1 直接返回 0。
2. 如果数组开头两个数字的大小关系确定了，数组之后的数值就都可以贪心求出了。
3. 首先枚举前两个数字的大小关系，有两种情况， nums[0] > nums[1] 或者 nums[0] < nums[1]。
4. 然后我们从第三个数字开始遍历。
5. 如果出现了 nums[i - 2] < nums[i - 1] <= nums[i] 的情况，我们就不得不将 nums[i] 调整到 num[i - 1] - 1。
6. 如果出现了 nums[i - 2] > nums[i - 1] >= nums[i] 的情况，我们就不得不将 nums[i - 1] 调整到 num[i] - 1。
7. 其余情况不变。

时间复杂度

• 只有常数种情况，每个情况都是线性遍历，故时间复杂度为 $O(n)$。

空间复杂度

• 每种情况需要一个额外的临时数组保存数字变化，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int solve(vector<int> nums) {
        int n = nums.size();
        int tot = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i - 2] < nums[i - 1] && nums[i - 1] <= nums[i]) {
                tot += nums[i] - nums[i - 1] + 1;
                nums[i] = nums[i - 1] - 1;
            }
            if (nums[i - 2] > nums[i - 1] && nums[i - 1] >= nums[i]) {
                tot += nums[i - 1] - nums[i] + 1;
                nums[i - 1] = nums[i] - 1;
            }
        }
        return tot;
    }

    int movesToMakeZigzag(vector<int>& nums) {
        int n = nums.size(), ans1, ans2;
        if (n == 1)
            return 0;
        int t0 = nums[0], t1 = nums[1];

        nums[1] = nums[0] <= nums[1] ? nums[0] - 1 : nums[1];
        ans1 = solve(nums) + t1 - nums[1];
        nums[1] = t1;

        nums[0] = nums[0] >= nums[1] ? nums[1] - 1 : nums[0];
        ans2 = solve(nums) + t0 - nums[0];

        return min(ans1, ans2);
    }
};