LeetCode 题解工作台
使数组成为递增数组的最少右移次数
给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。 一次 右移 指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。 示例 1： …
1
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
我们先用一个指针 从左到右遍历数组 ，找出一段连续的递增序列，直到 到达数组末尾或者 $nums[i - 1] \gt nums[i]$。接下来我们用另一个指针 从 $i + 1$ 开始遍历数组 ，找出一段连续的递增序列，直到 到达数组末尾或者 $nums[k - 1] \gt nums[k]$ 且 $nums[k] \gt nums[0]$。如果 到达数组末尾，说明数组已经是递增的，返…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。
一次 右移 指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。
示例 1：
输入：nums = [3,4,5,1,2] 输出：2 解释： 第一次右移后，nums = [2,3,4,5,1] 。 第二次右移后，nums = [1,2,3,4,5] 。 现在 nums 是递增数组了，所以答案为 2 。
示例 2：
输入：nums = [1,3,5] 输出：0 解释：nums 已经是递增数组了，所以答案为 0 。
示例 3：
输入：nums = [2,1,4] 输出：-1 解释：无法将数组变为递增数组。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100nums中的整数互不相同。
解题思路
方法一：直接遍历
我们先用一个指针 从左到右遍历数组 ，找出一段连续的递增序列，直到 到达数组末尾或者 。接下来我们用另一个指针 从 开始遍历数组 ，找出一段连续的递增序列，直到 到达数组末尾或者 且 。如果 到达数组末尾，说明数组已经是递增的，返回 ；否则返回 。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def minimumRightShifts(self, nums: List[int]) -> int:
n = len(nums)
i = 1
while i < n and nums[i - 1] < nums[i]:
i += 1
k = i + 1
while k < n and nums[k - 1] < nums[k] < nums[0]:
k += 1
return -1 if k < n else n - i
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) to scan for the pivot and validate shifts. Space complexity is O(1) since no extra storage is required beyond counters and indices. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if candidate identifies the rotation point efficiently.
- question_mark
Observes attention to handling arrays that cannot be sorted by rotation.
- question_mark
Watches for correct calculation of shift counts and validation.
常见陷阱
外企场景- error
Failing to detect multiple drops in the array causing incorrect shift calculation.
- error
Assuming the array is always sortable by a single rotation.
- error
Off-by-one errors when computing right shift amounts modulo array length.
进阶变体
外企场景- arrow_right_alt
Left shift rotations instead of right shifts with the same pivot logic.
- arrow_right_alt
Arrays containing duplicate values requiring careful validation.
- arrow_right_alt
Larger arrays requiring efficient O(n) scanning without extra space.