class Solution {
public:
int minimumRightShifts(vector<int>& nums) {
}
};
8039. 使数组成为递增数组的最少右移次数
给你一个长度为 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 中的整数互不相同。原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 15.8 MB, 提交时间: 2023-09-17 22:32:12
class Solution:
def minimumRightShifts(self, nums: List[int]) -> int:
i, n = 1, len(nums)
while i < n and nums[i - 1] < nums[i]:
i += 1
if i == n:
return 0
if nums[0] < nums[-1]:
return -1
mid = i
i += 1
while i < n and nums[i - 1] < nums[i]:
i += 1
if i < n:
return -1
return n - mid
# 暴力
def minimumRightShifts2(self, nums: List[int]) -> int:
for i in range(len(nums)):
if all(x < y for x, y in pairwise(nums)):
return i
nums = [nums[-1]] + nums[:-1]
return -1
golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2023-09-17 22:31:37
// 至多两段递增子数组
func minimumRightShifts(a []int) int {
i, n := 1, len(a)
for i < n && a[i-1] < a[i] {
i++
}
if i == n {
return 0
}
if a[0] < a[n-1] {
return -1
}
mid := i
i++
for i < n && a[i-1] < a[i] {
i++
}
if i < n {
return -1
}
return n - mid
}
// 暴力
func minimumRightShifts2(a []int) int {
for i := 0; i < len(a); i++ {
if sort.IntsAreSorted(a) {
return i
}
a = append(a[len(a)-1:], a[:len(a)-1]...)
}
return -1
}
java 解法, 执行用时: 1 ms, 内存消耗: 40 MB, 提交时间: 2023-09-17 22:30:52
class Solution {
public int minimumRightShifts(List<Integer> nums) {
int i = 0, n = nums.size();
while (i < n - 1 && nums.get(i) < nums.get(i + 1)) {
++i;
}
if (i == n - 1) {
return 0;
}
if (nums.get(n - 1) > nums.get(0)) {
return -1;
}
++i;
int j = i;
while (i < n - 1 && nums.get(i) < nums.get(i + 1)) {
++i;
}
if (i == n - 1) {
return n - j;
}
return -1;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 22.4 MB, 提交时间: 2023-09-17 22:30:41
class Solution {
public:
int minimumRightShifts(vector<int>& nums) {
int n = nums.size();
int flag = 0;
int ans = 0;
for (int i = 0; i < n; ++i) {
// 因为是循环右移，最后一个元素也要小于第一个元素
if (nums[i] > nums[(i + 1) % n]) {
// 第二次下降了
if (flag == 1) {
ans = -1;
break;
}
// 第一次下降
flag = 1;
// 剩下的都要右移
ans = n - i - 1;
}
}
return ans;
}
};