LeetCode 1144. 递减元素使数组呈锯齿状

原创

Yano_nankai

修改于 2021-02-25 10:27:21

4200

修改于 2021-02-25 10:27:21

文章被收录于专栏：二进制文集

题目描述

题目链接

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

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

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

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

示例 1：

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

示例 2：

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

解题思路

这道题第一眼看上去很难，但是细想一共就两种情况：

每个偶数索引对应的元素都大于相邻的元素
每个奇数索引对应的元素都大于相邻的元素

如果只是上述一种情况的话，就比较简单。题目需要将 2 种情况都计算一遍即可。

代码

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int oddNumberCount = 0;
        int evenNumberCount = 0;
        for (int i = 0; i < nums.length; i++) {
            int l = i - 1;
            int r = i + 1;
            int leftGap = 0;
            int rightGap = 0;
            //计算自身比左边大多少->自身需要递减几步能达到小于左边
            if (l >= 0) {
                leftGap = Math.max(nums[i] - nums[l] + 1, 0);
            }
            //计算自身比右边大多少->自身需要递减几步能达到小于右边
            if (r <= nums.length - 1) {
                rightGap = Math.max(nums[i] - nums[r] + 1, 0);
            }
            //如果自身时偶数，则 count 在偶数需要递减的次数
            if (i % 2 == 0) {
                evenNumberCount += Math.max(leftGap, rightGap);
            } else {
                //否则，则 count 在奇数需要递减的次数
                oddNumberCount += Math.max(leftGap, rightGap);
            }
        }
        //返回小值
        return Math.min(oddNumberCount, evenNumberCount);
    }
}