每日一题：递减元素使数组呈锯齿状（1144）

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

题意
思路

有两种锯齿状数组，我们分别求一下每种方式所需的最小递减次数，最后再求一个最小值即可。
遍历数组，对于遍历的第i个数， $nums[i]$ 不断减小到要比左右相邻数字都小，即要满足 $nums[i - 1] < nums[i] > nums[i + 1]$ , 所以 $nums[i]$ 要修改成 $min(nums[i - 1], nums[i + 1]) - 1$ , 修改次数为 $nums[i] - min(nums[i - 1], nums[i + 1]) + 1$ ，如果nums[i]本来就不超过 $m$ , 就无需修改。
因此，nums的修改次数为 $max(nums[i]−min(nums[i−1],nums[i+1])+1,0)$

代码

C++代码：

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        vector<int> res{0, 0};
        for(int i = 0; i < nums.size(); i++){
            int left = i ? nums[i - 1]: INT_MAX;
            int right = i < nums.size() - 1 ? nums[i + 1]: INT_MAX;
            res[i % 2] += max(0, nums[i] - min(left, right) + 1);
        }
        return *min_element(res.begin(), res.end());
    }
};

Python 代码

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        s = [0] * 2
        for i, x in enumerate(nums):
            left = nums[i - 1] if i else inf
            right = nums[i + 1] if i < len(nums) - 1 else inf
            s[i % 2] += max(0, x - min(left, right) + 1)
        return min(s)

总结

时间复杂度： $O(n)$ , 其中n为nums的长度。
空间复杂度： $O(1)$ , 禁用到若干额外变量。

每日一题：递减元素使数组呈锯齿状（1144）

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

推荐阅读更多精彩内容