数据结构与算法 #18 下跳棋，极富想象力的同向双指针模拟

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 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

问题抽象

概括问题目标：

求移动石头直到连续的最小和最大操作次数，每次操作只能选择端点石头，且只能移动到非端点位置。

分析问题要件：

• 限制条件 1：只能移动端点
• 限制条件 2：只能移动到非端点位置，即需要翻越其它石头，例如示例 [1,2,4] 或 [1,2,5] 中，不能移动右端点；
• 终止条件：如果左侧有空间，那么可以将右端点移动过去；如果右侧有空间，那么可以将左端点移动过去，因此当所有石头都连续时才无法继续移动。

提高抽象程度：

• 空位：当不是所有石头都连续时，数组元素中间一定存在空位，空位数 = [右端点 - 左端点 + 1 - n]。当空位数 = 0 时，无法继续移动。
• 决策模型：由于每次移动端点石头时，可以选择放位置到数组中间的空位上（满足限制条件 2），所以这是一个决策问题。

分析放置策略：

• 思路类似于同系列问题：1033. 移动石子直到连续
• 最大移动次数：为了放大移动次数，我们期望每次移动石头最多消耗一个空位；
• 最少移动次数：为了缩小移动次数，我们期望每次移动石头最好一步到位；

最大移动次数分析：

• 1、由于每次操作至少会消耗一个空位，所以最大操作次数不会高于空位个数；
• 2、由于限制条件 2，所以每次移动石头都会完全丢弃端点石头与最近石头中间的所有空位。因此，为了放大移动次数，每次移动端点石头时当且仅当放置到最近石头相邻的空位时，移动次数是最优的（否则，下次在移动端点石头时，会放弃中间的所有空位，而移动到相邻空位则不会放弃任何空位）；
• 3、在确定最大放置策略后，由于从第二次移动开始不会丢弃任何空位，所以可以直接根据「空位数」公式算出第二次以后的最大移动空位：
  • 如果第一次移动左端点（丢弃 stones[0] 到 stones[1] 的空位，只填满 stones[1] 到 stones[n-1] 的空位），那么总操作次数为 (stones[n-1]) - (stones[1]) + 1 - (n - 1)
  • 如果第一次移动右端点（丢弃 stones[n-1] 到 stone[n-2] 的空位），那么总操作次数为 stones[n-2] - stones[0] + 1 - (n - 1)

最小移动次数分析：

• 1、由于达到终止条件时所有石头都被放置在长度为 n 的窗口中，那么我们选择将游离的石头归集到石头最密集的区域时，能够缩小移动次数。具体来说，就是归集到长度为 n 的窗口中空位数最少得区域。此时，最小操作次数为 n - (石头数) = n - (j - i + 1)
• 2、由于限制条件 2，有特例 [1,2,3,6] 和 [1,4,5,6]，虽然窗口为 n 的空位数最少为 1，但总是需要 2 步才能移动完成。如 [1,2,3,6] -> [2,3,5,6] -> [3,4,5,6]。
• 3、由于限制条件 2，有特例 [1,2,3,5] 和 [2,4,5,6]，与上一条分析相似，但只要一次移动完成，由于这种特例能够被分析 1 覆盖，所以不需要特殊处理。

示意图

如何维护长度为 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)
    }
}

复杂度分析：

• 时间复杂度：$O(nlgn)$ 瓶颈来源于排序
• 空间复杂度：$O(lgn)$ 瓶颈来源于排序

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

• #1 链表问题总结
• #2 链表相交 & 成环问题总结
• #3 计算器与逆波兰表达式总结
• #4 高楼丢鸡蛋问题总结
• #5 为什么你学不会递归？谈谈我的经验
• #6 回溯算法解题框架总结
• #7 下次面试遇到二分查找，别再写错了
• #8 什么是二叉树？
• #9 什么是二叉堆 & Top K 问题
• #10 使用前缀和数组解决 “区间和查询” 问题
• #11 面试遇到线段树，已经这么卷了吗？
• #12 使用单调队列解决 “滑动窗口最大值” 问题
• #13 使用单调栈解决 “下一个更大元素” 问题
• #14 使用并查集解决 “朋友圈” 问题
• #15 如何实现一个优秀的 HashTable 散列表
• #16 简答一波 HashMap 常见面试题
• #17 二叉树高频题型汇总
• #18 下跳棋，极富想象力的同向双指针模拟
• #19 ChatGPT 通过谷歌算法面试，年薪 18.3 万美金

Java & Android 集合框架系列文章: 跳转阅读