题目描述：
给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。
一次 右移 指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。
数据范围：
$1\le nums.len \le 100$
题解：
首先找中断点，也就是 $nums[i + 1] < nums[i]$ 的点，如果找不到，也就是已经是升序了，直接返回 $0$ 。
找到了之后需要判断后面一段是不是一直升序，如果不是，直接返回 $-1$ 。
最后还要注意如果 $nums[n - 1] > nums[0]$ 不能拼起来，返回 $-1$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minimumRightShifts(vector<int> &nums)
{
int start = 0;
int n = nums.size();
bool flag = true;
while (start + 1 < n && nums[start + 1] > nums[start])
start++;
if(start == n - 1) return 0;
for (int i = start + 1; i < n - 1; ++i)
{
if (nums[i] > nums[i + 1])
{
flag = false;
break;
}
}
if (flag == false)
return -1;
start = n - start - 1;
if (nums[n - 1] > nums[0])
return -1;
return start;
}
};
|