问题:
给定一个数组stones代表每一块石头的位置,
每次可对两边界的两块石头调整位置,只能向非边界的位置移动。
求解,要最终使得所有的石头连续摆放(即他们的位置连续),最多和最少分别需要移动多少次?
Example 1: Input: [7,4,9] Output: [1,2] Explanation: We can move 4 -> 8 for one move to finish the game. Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game. Example 2: Input: [6,5,4,3,10] Output: [2,3] We can move 3 -> 8 then 10 -> 7 to finish the game. Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game. Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move. Example 3: Input: [100,101,104,102,103] Output: [0,0] Note: 3 <= stones.length <= 10^4 1 <= stones[i] <= 10^9 stones[i] have distinct values.
解法:
sliding windows
这里的windows则是我们想要的最终连续石头的位置。那么windows.size=A(stones).size
分类解决:
■1. 最多移动的次数:(most case)
分别从左右两边考虑,
leftmost:尽量让所有的石头都能成为左边界(如下图)
分两步:
step1:把A[0]放到A[1]的下一个空位。(尽量想让A[0]靠近左边,但是有且只能往非边界的位置放的话,只能是最近的A[1]的下一个空位)
step2:由于A[0]已经开始对A[1]下一个空位开始填充,那么,从A[1]开始,左边界逐次递增++1,一直到最后一位A[n-1]向前推windows.size-1个(window的开头元素)
上述两步合起来
step1:1 步
step2:A[n-1]-(n-1) - A[1] 步 (左窗口-A[1])
则有:
leftmost=A[n-1]-(n-1) - A[1] + 1;
rightmost同理可得:
step1:1 步
step2:A[n-2] - (A[0]+n-1) 步 (A[n-2]-右窗口)
rightmost=A[n-2] - (A[0]+n-1) + 1;
然后取左右两种可能的最大值。
most=max(leftmost, rightmost);
■2. 最少移动的次数:
又分两种情况:
一般case:(如下图黄框)
只需要尽量将窗口外的石头,移入窗口空位即可,这样最小移动次数,即是:窗口内空位的个数(==窗口外石头的个数)
角落case:
空位在左右边界的情况,由于不能直接用窗口外的石头填充空位,则需要至少移动 2 步。(如下图绿框)
我们要求最少移动的次数的话,则是求上述两种case中移动最少的情况,
一般case:则需要找到窗口内空位个数最少的情况
角落case:=定值 2
因此我们滑动窗口,窗口size确定,控制右窗口 j 从A[0]开始,往最后的A[n-1]滑动,
(用窗口size确定左窗口 i )
在这期间遍历所有的窗口可能,找到移动次数最少的可能。
参考代码:
1 class Solution { 2 public: 3 vector<int> numMovesStonesII(vector<int>& stones) { 4 sort(stones.begin(), stones.end()); 5 int n=stones.size(); 6 int most=0, least=INT_MAX; 7 //most: 8 int leftmost=stones[n-1]-(n-1) - stones[1] + 1; 9 int rightmost=stones[n-2] - (stones[0]+n-1) + 1; 10 most=max(leftmost, rightmost); 11 12 //least: find sliding windows[i~j]: which has the least space. 13 int i=0; 14 for(int j=0; j<n; j++){ 15 while(stones[j]-stones[i]>=n) i++; 16 //find A[i]~A[j] -> [windows.size==n] 17 if(j-(i-1)==(n-1) && stones[j]-stones[i]==(n-1)-1){ 18 //corner case: [1,2,3,4]...10: 19 //i=0,j=3 A[i]=1, A[j]=4 20 //size(i~j)=n-1, A[i]..A[j]->连续: A[j]-A[i]=size(i~j)-1=(n-1)-1 21 least=min(least, 2); 22 }else{ 23 //normal case: sum of spaces 24 //window:A[i]~A[j] 25 //totle size=n, sum of spaces=totle size-cout(A[i]..A[j]) 26 //=n-(j-(i-1)) 27 least=min(least, n-(j-(i-1))); 28 } 29 } 30 return {least, most}; 31 } 32 };