关于后端:数据结构与算法-18-下跳棋极富想象力的同向双指针模拟

5次阅读

共计 2919 个字符，预计需要花费 8 分钟才能阅读完成。

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

学习数据结构与算法的关键在于把握问题背地的算法思维框架，你的思考越形象，它能笼罩的问题域就越广，了解难度也更简单。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 18 篇文章，残缺文章目录请移步到文章开端~

这道题是 LeetCode 上的 1040. 挪动石子直到间断 II，难度是 Meduium，难度分是 2455。尽管是 Medium 题，然而打 Hard 标签一点也不为过。长期作为中等题的难度 Top1，直到去年被 [2289. 使数组按非递加顺序排列
](https://leetcode.cn/problems/steps-to-make-array-non-decreasing/) 题挤下来。

标签：模仿、贪婪、排序、同向双指针

三枚石子搁置在数轴上，地位别离为 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 汇合框架系列文章: 跳转浏览