Medium

题目描述

给你一个整数数组 nums，每次 移动 都是从中选择任意一个元素并将其减少 1。

数组 A 就是 锯齿数组，如果它满足下述条件之一：

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

返回将数组 nums 转换为锯齿数组所需的最少移动次数。

示例 1：

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

示例 2：

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

提示：

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

解题思路

这道题的关键思路是分别考虑两种锯齿状态：

  1. 偶数位置元素较大：A[0] > A[1] < A[2] > A[3] < …
  2. 奇数位置元素较大：A[0] < A[1] > A[2] < A[3] > …

对于第一种情况，我们需要让奇数位置的元素小于相邻的偶数位置元素；对于第二种情况，我们需要让偶数位置的元素小于相邻的奇数位置元素。

由于我们只能减少元素值，所以策略是：

  • 当某个位置的元素需要变小时，我们将其减少到刚好小于相邻元素的最小值
  • 具体来说，如果位置 i 需要变小，且其相邻元素的最小值为 minAdj，则需要减少的次数为 max(0, nums[i] - minAdj + 1)

算法流程：

  1. 分别计算两种情况下需要的移动次数
  2. 第一种情况：让奇数位置变小
  3. 第二种情况：让偶数位置变小
  4. 返回两种情况的最小值

时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int n = nums.size();
        int moves1 = 0, moves2 = 0;
        
        // 情况1：奇数位置变小
        for (int i = 1; i < n; i += 2) {
            int minAdj = nums[i-1];
            if (i + 1 < n) {
                minAdj = min(minAdj, nums[i+1]);
            }
            moves1 += max(0, nums[i] - minAdj + 1);
        }
        
        // 情况2：偶数位置变小
        for (int i = 0; i < n; i += 2) {
            int minAdj = INT_MAX;
            if (i > 0) minAdj = min(minAdj, nums[i-1]);
            if (i + 1 < n) minAdj = min(minAdj, nums[i+1]);
            if (minAdj != INT_MAX) {
                moves2 += max(0, nums[i] - minAdj + 1);
            }
        }
        
        return min(moves1, moves2);
    }
};

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        n = len(nums)
        moves1 = moves2 = 0
        
        # 情况1：奇数位置变小
        for i in range(1, n, 2):
            min_adj = nums[i-1]
            if i + 1 < n:
                min_adj = min(min_adj, nums[i+1])
            moves1 += max(0, nums[i] - min_adj + 1)
        
        # 情况2：偶数位置变小
        for i in range(0, n, 2):
            min_adj = float('inf')
            if i > 0:
                min_adj = min(min_adj, nums[i-1])
            if i + 1 < n:
                min_adj = min(min_adj, nums[i+1])
            if min_adj != float('inf'):
                moves2 += max(0, nums[i] - min_adj + 1)
        
        return min(moves1, moves2)

public class Solution {
    public int MovesToMakeZigzag(int[] nums) {
        int n = nums.Length;
        int moves1 = 0, moves2 = 0;
        
        // 情况1：奇数位置变小
        for (int i = 1; i < n; i += 2) {
            int minAdj = nums[i-1];
            if (i + 1 < n) {
                minAdj = Math.Min(minAdj, nums[i+1]);
            }
            moves1 += Math.Max(0, nums[i] - minAdj + 1);
        }
        
        // 情况2：偶数位置变小
        for (int i = 0; i < n; i += 2) {
            int minAdj = int.MaxValue;
            if (i > 0) minAdj = Math.Min(minAdj, nums[i-1]);
            if (i + 1 < n) minAdj = Math.Min(minAdj, nums[i+1]);
            if (minAdj != int.MaxValue) {
                moves2 += Math.Max(0, nums[i] - minAdj + 1);
            }
        }
        
        return Math.Min(moves1, moves2);
    }
}

var movesToMakeZigzag = function(nums) {
    const n = nums.length;
    let moves1 = 0, moves2 = 0;
    
    // 情况1：奇数位置变小
    for (let i = 1; i < n; i += 2) {
        let minAdj = nums[i-1];
        if (i + 1 < n) {
            minAdj = Math.min(minAdj, nums[i+1]);
        }
        moves1 += Math.max(0, nums[i] - minAdj + 1);
    }
    
    // 情况2：偶数位置变小
    for (let i = 0; i < n; i += 2) {
        let minAdj = Number.MAX_SAFE_INTEGER;
        if (i > 0) minAdj = Math.min(minAdj, nums[i-1]);
        if (i + 1 < n) minAdj = Math.min(minAdj, nums[i+1]);
        if (minAdj !== Number.MAX_SAFE_INTEGER) {
            moves2 += Math.max(0, nums[i] - minAdj + 1);
        }
    }
    
    return Math.min(moves1, moves2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次遍历一半的元素
空间复杂度O(1)只使用常数额外空间