Question

1144. Decrease Elements To Make Array Zigzag

中文文档

Description

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

 

Constraints:

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

Solutions

Solution 1: Enumeration + Greedy

We can separately enumerate the even and odd positions as the elements "smaller than adjacent elements", and then calculate the required number of operations. The minimum of the two is taken.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

class Solution:
  def movesToMakeZigzag(self, nums: List[int]) -> int:
    ans = [0, 0]
    n = len(nums)
    for i in range(2):
      for j in range(i, n, 2):
        d = 0
        if j:
          d = max(d, nums[j] - nums[j - 1] + 1)
        if j < n - 1:
          d = max(d, nums[j] - nums[j + 1] + 1)
        ans[i] += d
    return min(ans)

class Solution {
  public int movesToMakeZigzag(int[] nums) {
    int[] ans = new int[2];
    int n = nums.length;
    for (int i = 0; i < 2; ++i) {
      for (int j = i; j < n; j += 2) {
        int d = 0;
        if (j > 0) {
          d = Math.max(d, nums[j] - nums[j - 1] + 1);
        }
        if (j < n - 1) {
          d = Math.max(d, nums[j] - nums[j + 1] + 1);
        }
        ans[i] += d;
      }
    }
    return Math.min(ans[0], ans[1]);
  }
}

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

func movesToMakeZigzag(nums []int) int {
  ans := [2]int{}
  n := len(nums)
  for i := 0; i < 2; i++ {
    for j := i; j < n; j += 2 {
      d := 0
      if j > 0 {
        d = max(d, nums[j]-nums[j-1]+1)
      }
      if j < n-1 {
        d = max(d, nums[j]-nums[j+1]+1)
      }
      ans[i] += d
    }
  }
  return min(ans[0], ans[1])
}

function movesToMakeZigzag(nums: number[]): number {
  const ans: number[] = Array(2).fill(0);
  const n = nums.length;
  for (let i = 0; i < 2; ++i) {
    for (let j = i; j < n; j += 2) {
      let d = 0;
      if (j > 0) {
        d = Math.max(d, nums[j] - nums[j - 1] + 1);
      }
      if (j < n - 1) {
        d = Math.max(d, nums[j] - nums[j + 1] + 1);
      }
      ans[i] += d;
    }
  }
  return Math.min(...ans);
}

public class Solution {
  public int MovesToMakeZigzag(int[] nums) {
    int[] ans = new int[2];
    int n = nums.Length;
    for (int i = 0; i < 2; ++i) {
      for (int j = i; j < n; j += 2) {
        int d = 0;
        if (j > 0) {
          d = Math.Max(d, nums[j] - nums[j - 1] + 1);
        }
        if (j < n - 1) {
          d = Math.Max(d, nums[j] - nums[j + 1] + 1);
        }
        ans[i] += d;
      }
    }
    return Math.Min(ans[0], ans[1]);
  }
}