class Solution {
public:
int movesToMakeZigzag(vector<int>& nums) {
}
};
1144. 递减元素使数组呈锯齿状
给你一个整数数组 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 <= 10001 <= nums[i] <= 1000原站题解
javascript 解法, 执行用时: 60 ms, 内存消耗: 40.8 MB, 提交时间: 2023-02-27 09:36:23
/**
* @param {number[]} nums
* @return {number}
*/
var movesToMakeZigzag = function(nums) {
return Math.min(help(nums, 0), help(nums, 1));
}
const help = (nums, pos) => {
let res = 0;
for (let i = pos; i < nums.length; i += 2) {
let a = 0;
if (i - 1 >= 0) {
a = Math.max(a, nums[i] - nums[i - 1] + 1);
}
if (i + 1 < nums.length) {
a = Math.max(a, nums[i] - nums[i + 1] + 1);
}
res += a;
}
return res;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-02-27 09:36:05
func movesToMakeZigzag(nums []int) int {
help := func(pos int) int {
res := 0
for i := pos; i < len(nums); i += 2 {
a := 0
if i-1 >= 0 {
a = max(a, nums[i]-nums[i-1]+1)
}
if i+1 < len(nums) {
a = max(a, nums[i]-nums[i+1]+1)
}
res += a
}
return res
}
return min(help(0), help(1))
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a > b { return a }; return b }
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2023-02-27 09:35:10
'''
贪心+分类讨论
'''
class Solution:
def movesToMakeZigzag(self, nums: List[int]) -> int:
def help(pos: int) -> int:
res = 0
for i in range(pos, len(nums), 2):
a = 0
if i - 1 >= 0:
a = max(a, nums[i] - nums[i - 1] + 1)
if i + 1 < len(nums):
a = max(a, nums[i] - nums[i + 1] + 1)
res += a
return res
return min(help(0), help(1))
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-02-27 09:34:39
func movesToMakeZigzag(nums []int) int {
s := [2]int{}
for i, x := range nums {
left, right := math.MaxInt, math.MaxInt
if i > 0 {
left = nums[i-1]
}
if i < len(nums)-1 {
right = nums[i+1]
}
s[i%2] += max(x-min(left, right)+1, 0)
}
return min(s[0], s[1])
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
cpp 解法, 执行用时: 0 ms, 内存消耗: 7 MB, 提交时间: 2023-02-27 09:34:20
class Solution {
public:
int movesToMakeZigzag(vector<int> &nums) {
int s[2]{}, n = nums.size();
for (int i = 0; i < n; ++i) {
int left = i ? nums[i - 1] : INT_MAX;
int right = i < n - 1 ? nums[i + 1] : INT_MAX;
s[i % 2] += max(nums[i] - min(left, right) + 1, 0);
}
return min(s[0], s[1]);
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.9 MB, 提交时间: 2023-02-27 09:34:06
class Solution {
public int movesToMakeZigzag(int[] nums) {
int[] s = new int[2];
for (int i = 0, n = nums.length; i < n; ++i) {
int left = i > 0 ? nums[i - 1] : Integer.MAX_VALUE;
int right = i < n - 1 ? nums[i + 1] : Integer.MAX_VALUE;
s[i % 2] += Math.max(nums[i] - Math.min(left, right) + 1, 0);
}
return Math.min(s[0], s[1]);
}
}
python3 解法, 执行用时: 28 ms, 内存消耗: 15.1 MB, 提交时间: 2023-02-27 09:33:51
class Solution:
def movesToMakeZigzag(self, nums):
s = [0] * 2
for i, x in enumerate(nums):
left = nums[i - 1] if i > 0 else inf
right = nums[i + 1] if i < len(nums) - 1 else inf
s[i % 2] += max(x - min(left, right) + 1, 0)
return min(s)