数据结构与算法 #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、在确认最大放置战略后，因为从第2次移动开始不会丢掉任何空位，所以可以直接根据「空位数」公式算出第2次以后的最大移动空位：
  • 假如第一次移动左端点（丢掉 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 集合结构系列文章: 跳转阅览

LeetCode 上分之旅系列文章：跳转阅览

⭐️ 永久相信美好的工作即将产生，欢迎加入小彭的 Android 交流社群~