题目描述

Given an array nums of integers, a move consists of choosing any element and decreasing it by 1.

An array A is a zigzag array if either：

Every even-indexed element is greater than adjacent elements, ie. A[0] > A[1] < A[2] > A[3] < A[4] > …
OR, every odd-indexed element is greater than adjacent elements, ie. A[0] < A[1] > A[2] < A[3] > A[4] < …

Return the minimum number of moves to transform the given array nums into a zigzag array.

样例

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Example 2:

Input: nums = [9,6,1,6,2]
Output: 4

算法1

(一次遍历) $O(n)$

这道题可以直接通过一次遍历，分析两种不同zigzag形式的操作步骤数，最后返回步骤较小的数就行

时间复杂度分析：一次遍历 O(n)

C++ 代码

class Solution {
public:
     int movesToMakeZigzag(vector<int>& nums) {
        int n=nums.size();
        int ans1=0,ans2=0;
        for(int i=1;i<n-1;i++)
        {
            if(i%2==0) ans1+=max(0,nums[i]+1-min(nums[i-1],nums[i+1]));
            if(i%2==1) ans2+=max(0,nums[i]+1-min(nums[i-1],nums[i+1]));
        }
        ans1+=max(0,nums[0]+1-nums[1]);
        if((n-1)%2==0) ans1+=max(0,nums[n-1]+1-nums[n-2]);
        else ans2+=max(0,nums[n-1]+1-nums[n-2]);
        return min(ans1,ans2);
    }
};