使数组成为递增数组的最少右移次数

You are given a 0-indexed array nums of length n containing distinct positive integers. Return the minimum number of right shifts required to sort nums and -1 if this is not possible.

A right shift is defined as shifting the element at index i to index (i + 1) % n, for all indices.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 2
Explanation: 
After the first right shift, nums = [2,3,4,5,1].
After the second right shift, nums = [1,2,3,4,5].
Now nums is sorted; therefore the answer is 2.

Example 2:

Input: nums = [1,3,5]
Output: 0
Explanation: nums is already sorted therefore, the answer is 0.

Example 3:

Input: nums = [2,1,4]
Output: -1
Explanation: It's impossible to sort the array using right shifts.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums contains distinct integers.

/*
 题目思路：
 使用Java Stream来简化代码。
 利用Stream生成一个顺序流，模拟右移操作并判断是否为递增数组。
 使用IntStream.iterate生成从0到n的流，对每一个右移次数，生成一个新的数组，并检查其是否为递增。
 如果存在递增的情况，则返回相应的右移次数；否则，返回-1。
*/
import java.util.stream.IntStream;

public class SolutionStream {
    public int minRightShifts(int[] nums) {
        int n = nums.length;
        return IntStream.range(0, n)
                .filter(shift -> IntStream.range(0, n - 1)
                        .allMatch(i -> nums[(i + shift) % n] < nums[(i + shift + 1) % n]))
                .findFirst()
                .orElse(-1);
    }
}

该题解通过首先检查数组中的断点（即当前元素比前一个元素小的位置）来确定数组的非递增部分的起点。如果没有找到这样的断点，说明数组已经是递增的，直接返回0。找到断点后，算法检查从这个断点开始的数组是否可以通过一次循环变成递增数组。它通过遍历断点开始的数组，并检查是否每个元素都小于其后继元素来实现。如果在某点发现非递增序列，则返回-1，表示无法通过右移操作使数组递增。如果通过所有检查，返回从数组起始位置到断点的距离作为最小右移次数。

O(n)

O(1)