1040. Moving Stones Until Consecutive II¶
题目信息¶
- 题号:
1040
- 难度:
Medium
- 主题:
多个石子、端点移动、最少与最多步数
- 原题:
- 重点:
每次只能移动当前端点石子,且新位置必须使它在移动后不再是端点;返回所有石子连续所需的最少和最多步数
题目重述¶
数轴上有若干颗石子,位置由互不相同的数组 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,初始状态已经满足结束条件。