leetdode 1040. Moving Stones Until Consecutive I
题意：给一个数组，里面数都是独一无二的。
每次选择最大或者最小的数，将这个数变成不再是最大或者最小的次数。
求这个次数的最小值和最大值。
思路：
1：先算最大值
比如 3 4 6 8 1000
第一步，3变成4后面的空位置5,得到4 5 6 8 1000
第二步，4变成5后面的空位置7,得到5 6 7 8 1000
第三步，5变成6后面的空位置9,得到6 7 8 9 1000
。。。
也就是stone[0]变成stone[1]后面没有出现的过的数。
最终序列，如果所有数都忘左移，那么3是不变的，所有值都一步一步变小，变成 3 4 5 6 7；
如果所有数都忘右移，那么1000是不变的，所有值都一步一步变大，变成996 997 998 999 1000。
最大值是两种做法里，步数最多的。
怎么计算步数呢？
3 4 6 8 1000 变成 996 997 998 999 1000
考虑全往右移，那么1000是不能动的，先考虑最左边的，3变成(4,1000)的数，也就是最小的那个数会一步一步有空就插入。
里面一共有stone[n-1]-stone[1]-1个数，其中里面6,8两个数是已经存在，无法插空，也即是有n-3个数已经在这个区间；
那么我们的步数就是：总个数-已存在的数
也就是stone[n-1]-stone[1]-1 - (n-3)。
全部往左移，类似。stone[n-2]-stone[0]-1 - (n-3)
2：再算最小值
其实就是考虑一个区间。
以stone[j]为最右边的值，以n为区间长度，那么区间最小值是 stone[j]-n+1;
用stone[i]是该区间的第一个数。
和上面方法类似，只要这个区间里有多少数已经存在，就能知道多少步。
那么区间里的数总数是n，里面已经有的数j-i+1,需要的步数就是n-(j-i+1);
还有一个特例要考虑，n-1个数全连续，那么最小值应该是两步。
类似3 4 5 6 9
先变成4 5 6 8 9；
再变成4 5 6 7 8；
代码：
class Solution {
public:vector<int> numMovesStonesII(vector<int>& stones) {sort(stones.begin(), stones.end());int n = stones.size();int low=INT_MAX;int high = max(stones[n-1]-stones[1] - 1 - (n-3),stones[n-2]-stones[0] - 1 -(n-3) );//全部往左 和 全部往右比较int i = 0;for (int j = 0; j < n; j++){while (stones[j] - stones[i] >= n)i++;if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2) // n-1个数全连续low = min(low, 2);elselow = min(low, n - (j - i + 1));}return{low,high};}
};