题目描述
给你一个长度为 n
下标从 0 开始的数组 nums
,数组中的元素为 互不相同 的正整数。请你返回让 nums
成为递增数组的 最少右移 次数,如果无法得到递增数组,返回 -1
。
一次 右移 指的是同时对所有下标进行操作,将下标为 i
的元素移动到下标 (i + 1) % n
处。
样例
输入:nums = [3,4,5,1,2]
输出:2
解释:
第一次右移后,nums = [2,3,4,5,1]。
第二次右移后,nums = [1,2,3,4,5]。
现在 nums 是递增数组了,所以答案为 2。
输入:nums = [1,3,5]
输出:0
解释:nums 已经是递增数组了,所以答案为 0。
输入:nums = [2,1,4]
输出:-1
解释:无法将数组变为递增数组。
限制
1 <= nums.length <= 100
1 <= nums[i] <= 100
nums
中的整数互不相同。
算法
(思维题) $O(n)$
- 找到数组中第一个出现递减的位置 $j$。如果 $j$ 不存在,则返回 $0$。
- 继续从 $j$ 开始遍历剩余的部分,如果再次出现递减,则说明无法将数组变为递增数组,返回 $-1$。
- 如果没有再出现递减,且末尾元素小于开头的元素,返回 $n - j$,因为需要移动数组直到以 $j$ 开头。否则返回 $-1$。
时间复杂度
- 遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minimumRightShifts(vector<int>& nums) {
const int n = nums.size();
int j = -1;
for (int i = 1; i < n; i++)
if (nums[i] < nums[i - 1]) {
j = i;
break;
}
if (j == -1)
return 0;
for (int i = j + 1; i < n; i++)
if (nums[i] < nums[i - 1])
return -1;
if (nums[n - 1] > nums[0])
return -1;
return n - j;
}
};