1040. Moving Stones Until Consecutive II

题目信息

题号:

1040

难度:

Medium

主题:

多个石子、端点移动、最少与最多步数

原题:

LeetCode 1040

重点:

每次只能移动当前端点石子,且新位置必须使它在移动后不再是端点;返回所有石子连续所需的最少和最多步数

题目重述

数轴上有若干颗石子,位置由互不相同的数组 stones 给出。每次操作选择当前最左或最右的端点石子,把它移动到一个未占用的整数位置;移动完成后,该石子必须严格位于新的最左和最右石子之间,不能继续作为端点。

当所有石子占据一段连续整数位置时结束。返回 [minimum, maximum],分别表示通过不同合法策略结束所需的最少和最多移动次数。

3 <= stones.length <= 10^4,1 <= stones[i] <= 10^9,所有位置互不相同。

自建示例

最少与最多移动次数相同:

输入:stones = [1,4,5,8]
输出:[2,2]
解释:先把端点 1 移到 6,得到 4、5、6、8;再把端点 4 移到 7,得到连续位置 5、6、7、8。任何合法策略都恰好需要两步。

所有石子已经连续:

输入:stones = [6,4,5]
输出:[0,0]
解释:排序后的位置为 4、5、6,初始状态已经满足结束条件。