LeetCode 题解工作台
递减元素使数组呈锯齿状
给你一个整数数组 nums ，每次 操作 会从中选择一个元素并 将该元素的值减少 1 。 如果符合下列情况之一，则数组 A 就是 锯齿数组 ： 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] A[3] ... 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] A[2] …
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们可以分别枚举偶数位和奇数位作为“比相邻元素小”的元素，然后计算需要的操作次数。取两者的最小值即可。 时间复杂度 ，其中 为数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一：枚举 + 贪心
我们可以分别枚举偶数位和奇数位作为“比相邻元素小”的元素，然后计算需要的操作次数。取两者的最小值即可。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def movesToMakeZigzag(self, nums: List[int]) -> int:
ans = [0, 0]
n = len(nums)
for i in range(2):
for j in range(i, n, 2):
d = 0
if j:
d = max(d, nums[j] - nums[j - 1] + 1)
if j < n - 1:
d = max(d, nums[j] - nums[j + 1] + 1)
ans[i] += d
return min(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is visited twice (once per pattern) with constant-time calculations. Space complexity is O(1) since calculations are done in-place without extra structures beyond counters. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate separates even and odd index patterns without merging logic.
- question_mark
Candidate applies minimal necessary decrements to satisfy local zigzag conditions.
- question_mark
Candidate correctly returns the smaller move count between two independent patterns.
常见陷阱
外企场景- error
Decreasing elements more than needed, inflating the move count.
- error
Only checking one index pattern and missing the globally minimal solution.
- error
Failing to correctly handle edge neighbors at array boundaries.
进阶变体
外企场景- arrow_right_alt
Compute zigzag moves where only adjacent differences matter, not absolute values.
- arrow_right_alt
Allow increases as well as decreases to achieve zigzag minimal moves.
- arrow_right_alt
Handle circular arrays where first and last elements are neighbors.