Leetcode 1144: Decrease Elements To Make Array Zigzag

https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/description/ 


Notes:

The key point is that we can only decease the elements, and each time we can decrease the elements by 1.

The optimal operation is that we just need to adjust only the one on the odd positions, or the one on the even positions.

The way to prove it as the following:

Let say we have adjusted the elements on both even and odd positions to finish the zigzag of the array. If (a) if the odd ones are higher than their even neighbors, the odds one are not necessary to be adjusted, or without the adjustment, the odds are still higher; (b) the argument is also applicable to the opposite case. Thus, only odd or even elements are needed for the adjustment.

See the code below,

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int res1 = 0, res2 = 0, len = nums.size();
        for(int i=0; i<len; i +=2) {//make the even lower;
            int a = 0;
            if(i>0) a = max(a, nums[i] - nums[i-1] + 1);
            if(i+1<len) a = max(a, nums[i] - nums[i+1] + 1);
            res1 += a;
        }
        for(int i=1; i<len; i +=2) {//make the odd lower;
            int a = 0;
            if(i>0) a = max(a, nums[i] - nums[i-1] + 1);
            if(i+1<len) a = max(a, nums[i] - nums[i+1] + 1);
            res2 += a;
        }
        return min(res1, res2);
    }
};