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

链接：1144.递减元素使数组呈锯齿状
难度：Medium
标签：贪心、数组
简介：返回将数组 nums 转换为锯齿数组所需的最小操作次数。

题解 1 - cpp

• 编辑时间：2023-02-27
• 内存消耗：7MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        return min(try1(nums), try2(nums));
    }
    int try1(vector<int> &nums) {
        int res = 0;
        for (int i = 1; i < nums.size(); i += 2) {
            int p = nums[i - 1];
            if (i + 1 < nums.size()) p = min(p, nums[i + 1]);
            if (nums[i] >= p) res += nums[i] - p + 1;
        }
        return res;
    }
    int try2(vector<int> &nums) {
        int res = 0;
        if (nums[0] >= nums[1]) res += nums[0] - nums[1] + 1;
        for (int i = 2; i < nums.size(); i += 2) {
            int p = nums[i - 1];
            if (i + 1 < nums.size()) p = min(p, nums[i + 1]);
            if (nums[i] >= p) res += nums[i] - p + 1;
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-02-27
• 执行用时：32ms
• 内存消耗：14.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
  
        def try1():
            res = 0
            for i in range(1, n, 2):
                p = nums[i-1]
                if i+1 < n:
                    p = min(p, nums[i+1])
                if nums[i] >= p:
                    res += nums[i] - p + 1
            return res
  
        def try2():
            res = 0
            if nums[0] >= nums[1]:
                res += nums[0] - nums[1] + 1
            for i in range(2, n, 2):
                p = nums[i - 1]
                if i + 1 < n:
                    p = min(p, nums[i + 1])
                if nums[i] >= p:
                    res += nums[i] - p + 1
            return res
        return min(try1(), try2())

题解 3 - rust

• 编辑时间：2023-02-27
• 内存消耗：1.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn moves_to_make_zigzag(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 1 {
            0
        } else {
            let try1 = || {
                let mut res = 0;
                let mut i = 1;
                while i < n {
                    let mut p = nums[i - 1];
                    if i + 1 < n {
                        p = p.min(nums[i + 1]);
                    }
                    if nums[i] >= p {
                        res += nums[i] - p + 1;
                    }
                    i += 2;
                }
                res
            };
            let try2 = || {
                let mut res = 0;
                if nums[0] >= nums[1] {
                    res += nums[0] - nums[1] + 1;
                }
                let mut i = 2;
                while i < n {
                    let mut p = nums[i - 1];
                    if i + 1 < n {
                        p = p.min(nums[i + 1]);
                    }
                    if nums[i] >= p {
                        res += nums[i] - p + 1;
                    }
                    i += 2;
                }
                res
            };
            try1().min(try2())
        }
    }
}