学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭将基于 Java / Kotlin 语言,为你分享常见的数据结构与算法问题,及其解题框架思路。
本文是数据结构与算法系列的第 18 篇文章,完整文章目录请移步到文章末尾~
这道题是 LeetCode 上的 1040. 移动石子直到连续 II,难度是 Meduium,难度分是 2455。虽然是 Medium 题,但是打 Hard 标签一点也不为过。长期作为中等题的难度 Top1,直到去年被 2289. 使数组按非递减顺序排列
题挤下来。
标签:模拟、贪心、排序、同向双指针
三枚石子放置在数轴上,位置分别为 a,b,c。
每一回合,你可以从两端之一拿起一枚石子(位置最大或最小),并将其放入两端之间的任一空闲位置。形式上,假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子,并将该石子移动到某一整数位置 k 处,其中 x < k < z 且 k != y。
当你无法进行任何移动时,即,这些石子的位置连续时,游戏结束。
要使游戏结束,你可以执行的最小和最大移动次数分别是多少? 以长度为 2 的数组形式返回答案:answer = [minimum_moves, maximum_moves]
示例 1:
输入:a = 1, b = 2, c = 5 输出:[1, 2] 解释:将石子从 5 移动到 4 再移动到 3,或者我们可以直接将石子移动到 3。
示例 2:
输入:a = 4, b = 3, c = 2 输出:[0, 0] 解释:我们无法进行任何移动。
提示:
1 <= a <= 100 1 <= b <= 100 1 <= c <= 100 a != b, b != c, c != a
概括问题目标:
求移动石头直到连续的最小和最大操作次数,每次操作只能选择端点石头,且只能移动到非端点位置。
分析问题要件:
提高抽象程度:
分析放置策略:
最大移动次数分析:
最小移动次数分析:
示意图
如何维护长度为 n 的滑动窗口:
同向双指针:
for(i in nums 索引) { while (j < n - 1 && 移动后窗口不大于 n) j++ }
class Solution { fun numMovesStonesII(stones: IntArray): IntArray { val n = stones.size // 排序 stones.sort() // 最大移动次数 val max1 = stones[n - 1] - stones[1] + 1 - (n - 1) val max2 = stones[n - 2] - stones[0] + 1 - (n - 1) val maxOp = Math.max(max1, max2) // 最小移动次数 var minOp = n var j = 0 // 枚举左端点 for (i in 0 until n) { while (j < n - 1 && stones[j + 1] - stones[i] + 1 <= n) j++ if (n - (j - i + 1) == 1 /* 窗口空位数 == 1 */ && stones[j] - stones[i] + 1 == n - 1 /* 窗口石头数 == n - 1 */) { minOp = Math.min(minOp, 2) } else { minOp = Math.min(minOp, n - (j - i + 1) /* 窗口空位数 */) } } return intArrayOf(minOp, maxOp) } }
复杂度分析: