【leetcode】1144. Decrease Elements To Make Array Zigzag

题目如下：

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

解题思路：本题无外乎两种情况，一种是nums[0] > nums[1]，另一种是nums[0] < nums[1]，把这两种情况计算一遍求较小值即可。在计算过程中，如果要求nums[i] > nums[i-1]，那么把nums[i-1] 减到nums[i] - 1；如果要求nums[i] < nums[i-1]，则把nums[i]减少到nums[i-1] - 1。

代码如下：

class Solution(object):

    def movesToMakeZigzag(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        # flag -  0: decrease; 1:increase

        def process(flag,nums):

            count = 0

            for i in range(1, len(nums)):

                if flag == 0 and nums[i] >= nums[i - 1]:

                    count += (nums[i] - nums[i - 1] + 1)

                    nums[i] = nums[i - 1] - 1

                elif flag == 1 and nums[i] <= nums[i - 1]:

                    count += (nums[i - 1] - nums[i] + 1)

                    nums[i - 1] = nums[i] - 1

                flag = not flag

            return count

        #nums[0] > nums[1]

        res = process(0,nums[::])

        # nums[1] > nums[0]

        res = min(res,process(1,nums))

        return res

巴特西

【leetcode】1144. Decrease Elements To Make Array Zigzag

最新文章

热门文章