标签: 数组
难度: Easy
给你一个长度为 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 中的整数互不相同。运行时间: 28 ms
内存: 16.0 MB
class Solution:
def minimumRightShifts(self, nums: List[int]) -> int:
n=len(nums)
s = -1
for i in range(n-1):
if nums[i+1] < nums[i]:
s = i+1
break
if s <0:
return 0
for i in range(n-1):
if nums[(s+i)%n] > nums[(s+i+1)%n]:
return -1
return n-s
该题解通过首先检查数组中的断点（即当前元素比前一个元素小的位置）来确定数组的非递增部分的起点。如果没有找到这样的断点，说明数组已经是递增的，直接返回0。找到断点后，算法检查从这个断点开始的数组是否可以通过一次循环变成递增数组。它通过遍历断点开始的数组，并检查是否每个元素都小于其后继元素来实现。如果在某点发现非递增序列，则返回-1，表示无法通过右移操作使数组递增。如果通过所有检查，返回从数组起始位置到断点的距离作为最小右移次数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minimumRightShifts(self, nums: List[int]) -> int:
n = len(nums) # 数组长度
s = -1 # 用于记录数组的非递增断点位置
# 寻找第一个非递增的位置
for i in range(n-1):
if nums[i+1] < nums[i]:
s = i+1
break
# 如果没有找到非递增的断点，说明数组已经是递增的
if s < 0:
return 0
# 从断点开始检查是否能通过完整循环变为递增数组
for i in range(n-1):
if nums[(s+i)%n] > nums[(s+i+1)%n]:
return -1 # 无法通过右移变为递增
# 返回需要的最小右移次数
return n - s
在题解中，非递增断点的位置是通过遍历数组并检查每对相邻元素来确定的。如果找到第一对相邻元素，其中后一个元素小于前一个元素，那么后一个元素的位置被标记为非递增断点。这种方法在确定首个非递增断点上是准确的，因为它直接响应数组中第一个出现逆序的位置。然而，它仅关注第一个逆序点，可能会忽略后续的逆序情况，但对于解决这个特定问题是足够的。
是的，这个结论对所有情况都适用，包括数组中只有一个元素的情况。如果数组只有一个元素，由于没有相邻的元素比较，自然不会存在元素小于前一个元素的情况，因此，这样的单元素数组默认是递增的，返回0移动次数是正确的。
表达式`(s+i)%n`用于循环访问数组，确保算法可以从断点处开始检查并绕回数组的起始处继续比较。这种循环访问方法理论上适用于任何情况，不会出现问题，只要数组的长度`n`是正整数。这种方法确保即使索引超过数组长度，也能正确地回到数组的开始，进行循环比较。
是的，题解中的方法确实意味着即使部分元素通过右移可以形成递增序列，如果整个数组不能通过一次完整的循环检查形成完全的递增序列，则整体会判定为失败，返回-1。这种方法确保只有当整个数组可以通过单次右移变为递增时才认为操作成功。这样做是为了确保解决方案的全局有效性，而不仅仅是局部的递增。