此题非常考验分析推理的能力,和编程技巧本身的关系倒是不大。
要使得操作数尽可能地多,我们需要将end point的石头填充到下一个最靠外的空缺(但这个空缺本身不能是end point)。这样,每动一步只消灭一个最靠外的空缺,就能够使得这个move足够缓慢。举个例子:
OOXXXOO
1234567
我们的方案就是将7移动到5,消灭一个最靠外的空缺;然后将6移动到4,再消灭一个此时最靠外的空缺;然后将5移动到3,再消灭一个此时最靠外的空缺...以此类推,每移动一步,我们就消灭一个空缺,因此总移动的步数,就是被初始状态的石头所“内含”的空缺个数。
但是这个有一个特殊情况
OOXXXOXO
12345678
此时第一步不允许将8移动到7.根据要求8只能移动到5,然后转换为
OOXXOO
123456
此时我们就可以放心地用上运用之前的规律:需要移动的步数,就是此时"内含“的空缺数2。所以结论就是stones[n-2]-stones[0]+1-(n-1)
当然,上面的公式考虑的是移动右边的石头往左边填充。反过来也可以考虑移动左边的石头往右边填充:stones[n-1]-stones[1]+1-(n-1)
最终max move是两者取最大值。
min move的基本思想是:我们尽量找初始状态下分布就相对集中靠拢的区域,尝试将其他的石头直接搬往这个区域的两边。举个例子:
OOXOOXXXO
123456789
我们发现1-5这个区间里面就有四个石头,显然直接将9搬到3就可以将区间1-5填满。所以这就提示我们寻找一个长度为n的sliding window,里面的石头越多越有利。理想情况下,我们只需要搬运n-(这个长度为n的窗口里的石头数)
但是同样有一个特殊情况
OOOOXXXXO
123456789
这个时候,虽然1-5这个区间里面有四块石头,是最理想的聚集区,但是,我们无法直接将9移动到5.这是因为这个“理想聚集区”的右端点5这个位置,目前是空缺,并且窗口的右侧只有一个石头。此时我们只有多操作一步,将1移动到6,形成
OOOXOXXO
123456789
的局面,使得理想聚集区变成了[2-6],然后再使用上面的规则:搬运n-(这个长度为n的窗口里的石头数)
次,将9移动到5即可。事实上,这种特殊情况只有在n-1个石头连续排放的时候才会出现,因此操作数就是2。
所以,处理min move的逻辑是:
for i =0; i<n; i++ // 大框架是遍历窗口的左端的位置
{
找到j,使得stones[j]-stones[i]+1>=n.
if stones[j]-stones[i]+1==n
说明从stones[i]到stones[j]这个窗口正好有n个位置,并且窗口的最右端是块石头,
所以我们只要搬运```n-(这个长度为n的窗口里的石头数)```次,即```n-(j-i+1)```
else
说明从stones[i]开始的长度为n的窗口,最右端不是石头
if (j-i==n-1)
说明是分析到的特殊情况,n-1个石头连排,答案返回2
else
说明是一般的情况,所以我们只要搬运```n-(这个长度为n的窗口里的石头数)```次,即```n-(j-i)```
}