关于android:LeetCode-周赛-34320230430结合下一个排列的贪心构造问题

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。

大家好，我是小彭。

明天是五一假期的第二天，打周赛的人数比前一天的双周赛多了，难道大家都只玩一天吗？这场周赛是 LeetCode 第 343 场单周赛，如果不思考第一题摆烂的翻译，整体题目品质还是很不错哒。

往期回顾：LeetCode 双周赛第 103 场 · 区间求和的树状数组经典利用

周赛概览

Q1. 保龄球游戏的获胜者（Easy）

标签：数组、模仿、计数

Q2. 找出叠涂元素（Medium）

标签：矩阵、散列表、计数

Q3. 返回指标的最小代价（Medium）

标签：最短路、Dijkstra、最小堆

Q4. 字典序最小的漂亮字符串（Hard）

标签：贪婪、结构

Q1. 保龄球游戏的获胜者（Easy）

https://leetcode.cn/problems/determine-the-winner-of-a-bowling-game/

题目形容

给你两个下标从 0 开始的整数数组 player1 和 player2，别离示意玩家 1 和玩家 2 击中的瓶数。

保龄球较量由 n 轮组成，每轮的瓶数恰好为 10。

假如玩家在第 i 轮中击中 xi 个瓶子。玩家第 i 轮的价值为：

• 如果玩家在前两轮中击中了 10 个瓶子，则为 2xi。
• 否则，为 xi。

玩家的得分是其 n 轮价值的总和。

返回

• 如果玩家 1 的得分高于玩家 2 的得分，则为 1；
• 如果玩家 2 的得分高于玩家 1 的得分，则为 2；
• 如果平局，则为 0。

示例 1：

输出：player1 = [4,10,7,9], player2 = [6,5,2,3]
输入：1
解释：player1 的得分是 4 + 10 + 2*7 + 2*9 = 46。player2 的得分是 6 + 5 + 2 + 3 = 16。player1 的得分高于 player2 的得分，所以 play1 在较量中获胜，答案为 1。

示例 2：

输出：player1 = [3,5,7,6], player2 = [8,10,10,2]
输入：2
解释：player1 的得分是 3 + 5 + 7 + 6 = 21。player2 的得分是 8 + 10 + 2*10 + 2*2 = 42。player2 的得分高于 player1 的得分，所以 play2 在较量中获胜，答案为 2。

示例 3：

输出：player1 = [2,3], player2 = [4,1]
输入：0
解释：player1 的得分是 2 + 3 = 5。player2 的得分是 4 + 1 = 5。player1 的得分等于 player2 的得分，所以这一场较量平局，答案为 0。

提醒：

• n == player1.length == player2.length
• 1 <= n <= 1000
• 0 <= player1[i], player2[i] <= 10

题解（模仿）

简略模拟题，但题目形容的中文翻译有歧义，而且不能依据示例辨别进去：

• 了解 1：只有最开始的两轮中击中了 10 个瓶子，那么后续得分加倍；
• 了解 2：任意轮的前两轮中击中了 10 个瓶子，那么该轮得分加倍。

依照了解 2 模仿即可：

class Solution {fun isWinner(player1: IntArray, player2: IntArray): Int {
        var cnt1 = 0
        var cnt2 = 0
        for (i in player1.indices) {val mul1 = player1.slice(Math.max(0, i - 2) until i).any {it == 10}
            val mul2 = player2.slice(Math.max(0, i - 2) until i).any {it == 10}

            cnt1 += if (mul1) 2 * player1[i] else player1[i]
            cnt2 += if (mul2) 2 * player2[i] else player2[i]
        }
        return if (cnt1 == cnt2) 0 else if (cnt1 > cnt2) 1 else 2
    }
}

复杂度剖析：

• 工夫复杂度：$O(n)$ 其中 n 是 player1 数组的长度；
• 空间复杂度：$O(1)$ 仅应用常量级别空间。

Q2. 找出叠涂元素（Medium）

https://leetcode.cn/problems/first-completely-painted-row-or-column/

题目形容

给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵  mat。arr 和 mat 都蕴含范畴 [1，m * n] 内的  所有 整数。

从下标 0 开始遍历 arr 中的每个下标 i，并将蕴含整数 arr[i] 的 mat 单元格涂色。

请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素，并返回其下标 i。

示例 1：

输出：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输入：2
解释：遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。

示例 2：

输出：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输入：3
解释：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。

提醒：

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= arr[i], mat[r] <= m * n
• arr 中的所有整数 互不雷同
• mat 中的所有整数 互不雷同

问题结构化

1、概括问题指标

计算涂满一行或一列时的最小下标。

2、察看数据特色

arr 数组和 mat 矩阵中的所有整数都没有反复数。

3、剖析问题要件

• 涂色：应用 arr 数组对 mat 矩阵涂色；
• 终止条件：当存在一行或一列被涂满时，返回以后的 arr 数组下标。

至此，程序整体框架确定：

for (数字 in arr 数组) {
    涂色
    if (涂满一行或一列) 返回索引
}
return -1 // 问题肯定有解

4、进步形象水平

• 查找：对 mat 矩阵中的雷同数字的单元格涂色时，须要查找数字在矩阵中的地位：
• 计数：联合「无反复数」的数据特色，判断是否存在一行或一列被涂满时，就是判断一行或一列中被涂色的计数是否达到行数或列数。

5、具体化解决伎俩

如何查找数字的地位？

• 伎俩 1（暴力枚举）：枚举 mat 矩阵，直到匹配指标数字时进行；
• 伎俩 2（散列表）：联合「无反复数」的数据特色，能够预处理 mat 矩阵取得数字和地位的映射关系，在涂色时以 O(1) 工夫复杂度定位涂色地位。

如何判断达到终止条件？

• 伎俩 1（暴力枚举）：枚举 mat 矩阵的行列，当一行或一列的涂色个数达到行数或列数时进行；
• 伎俩 2（计数数组）：记录每一行和每一列的涂色计数，当计数达到行数或列数时，阐明达到终止条件。

题解（散列表 + 计数）

题目的要害信息是「无反复数」，依据问题剖析模仿即可：

class Solution {fun firstCompleteIndex(arr: IntArray, mat: Array<IntArray>): Int {
        val n = mat.size
        val m = mat[0].size
        // 计数数组
        val rows = IntArray(n)
        val columns = IntArray(m)
        // 散列表
        val hashMap = HashMap<Int, IntArray>()
        // 预处理
        for (i in 0 until n) {for (j in 0 until m) {hashMap[mat[i][j]] = intArrayOf(i, j)
            }
        }
        // 涂色
        for ((i, e) in arr.withIndex()) {val node = hashMap[e]!!
            // 判断
            if (++rows[node[0]] == m || ++columns[node[1]] == n) return i
        }
        return -1
    }
}

复杂度剖析：

• 工夫复杂度：$O(nm)$ 其中 n 和 m 别离为矩阵的行数和列数，预处理和涂色别离对每个元素拜访 1 次；
• 空间复杂度：$O(nm)$ 散列表和计数数组空间。

Q3. 返回指标的最小代价（Medium）

https://leetcode.cn/problems/minimum-cost-of-a-path-with-special-roads/

题目形容

给你一个数组 start，其中 start = [startX, startY] 示意你的初始地位位于二维空间上的 (startX, startY)。另给你一个数组 target，其中 target = [targetX, targetY] 示意你的指标地位 (targetX, targetY)。

从地位 (x1, y1) 到空间中任一其余地位 (x2, y2) 的代价是 |x2 - x1| + |y2 - y1|。

给你一个二维数组 specialRoads，示意空间中存在的一些非凡门路。其中 specialRoads[i] = [x1i, y1i, x2i, y2i, costi] 示意第 i 条非凡门路能够从 (x1i, y1i) 到 (x2i, y2i)，但老本等于 costi。你能够应用每条非凡门路任意次数。

返回从 (startX, startY) 到 (targetX, targetY) 所需的最小代价。

示例 1：

输出：start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
输入：5
解释：从 (1,1) 到 (4,5) 的最优门路如下：- (1,1) -> (1,2)，挪动的代价是 |1 - 1| + |2 - 1| = 1。- (1,2) -> (3,3)，挪动应用第一条非凡门路，代价是 2。- (3,3) -> (3,4)，挪动的代价是 |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5)，挪动应用第二条非凡门路，代价是 1。总代价是 1 + 2 + 1 + 1 = 5。能够证实无奈以小于 5 的代价实现从 (1,1) 到 (4,5)。

示例 2：

输出：start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
输入：7
解释：最优门路是不应用任何非凡门路，间接以 |5 - 3| + |7 - 2| = 7 的代价从初始地位达到指标地位。

提醒：

• start.length == target.length == 2
• 1 <= startX <= targetX <= 105
• 1 <= startY <= targetY <= 105
• 1 <= specialRoads.length <= 200
• specialRoads[i].length == 5
• startX <= x1i, x2i <= targetX
• startY <= y1i, y2i <= targetY
• 1 <= costi <= 105

准备常识 · 最短路算法

这道题是最短路问题，先回顾下几种最短路算法的区别：

• Floyd 算法（多源汇正权最短路）

  • 实用于求任意节点之间的最短路，须要三层循环枚举直达点 i、枚举终点 j 和枚举起点 k，工夫复杂度最高。

• Bellman Ford 算法（单源负权最短路）

  • 在每一轮迭代中，尝试对图上每一条边进行松弛，直到没有松弛操作时完结。

• Dijkstra 算法（单源正权最短路）：

  • 在每一轮迭代中，应用确定集中最短路长度最小的节点去松弛相邻节点，因为负权边会毁坏贪婪策略的抉择，无奈解决负权问题；
  • 稠密图小顶堆的写法更优，浓密图奢侈写法更优。

其中 n 是节点数，m 是边数。

问题结构化

1、概括问题指标

计算从 start 到 target 节点的最小代价。

2、察看数据特色

• 数据大小：节点数据范畴的上界是 10^5，相比于节点范畴，非凡门路最多只有 200 条，非凡门路是稠密的。

3、剖析问题要件

以 start 为终点，target 为起点，在每次操作能够从 from 节点挪动到 to 节点，破费的代价是 |x2 – x1| + |y2 – y1|，另外二维立体中有一些非凡门路，破费的代价是非凡的。

4、进步形象水平

• 曼哈顿间隔：破费的代价是 |x2 – x1| + |y2 – y1| 就是两个节点之间的曼哈顿间隔；
• 正权边：「从 from 节点挪动到 to 节点的代价 x」等价于「从 from 节点到 to 节点的边权为 x」；
• 有向边：因为题目形容非凡门路只能从 (x1, y1) 走到 (x2, y2)，因而题目是有向边；
• 是否为决策问题？因为每次操作有多种挪动地位抉择，因而这是决策问题，精确来说是最短路问题；
• 总结：这是一道图的单源正权有向边的最短路问题。

5、具体化解决方案

如何解决图的单源正权最短路问题？

这道题只须要计算从 start – target 之间的最短路问题，而且边是非负权边，合乎 Dijkstra 算法的利用场景。Dijkstra 算法的实质是贪婪 + BFS，咱们须要将所有节点分为 2 类，在每一轮迭代中，咱们从“候选集”中抉择间隔终点最短路长度最小的节点，因为该点不存在更优解，所以能够用该点来“松弛”相邻节点。

• 1、确定集：已确定（从终点开始）到以后节点最短门路的节点；
• 2、候选集：未确定（从终点开始）到以后节点最短门路的节点。

须要思考哪些节点？

这道题没有限度只能走非凡门路，那么是不是二维立体上所有节点都须要思考在呢？其实须要，联合「三角不等式」察看，咱们发现两个点间断走两次曼哈顿间隔没有意义，也就是说，指标门路肯定是在终点、起点和非凡门路节点两头挪动。

• 策略 1：从 from 到 to 走曼哈顿间隔；
• 策略 2：先从 from 走到非凡门路终点，走完非凡门路后再走曼哈顿间隔；
• 策略 3（没有意义）：先从 from 走曼哈顿间隔到 x，再从 x 走曼哈顿间隔到 to。

如何示意二维节点？

最简略的办法是通过位移将 (x, y) 压缩为一个惟一整数，因为这道题的坐标范畴最大到 10^5，所以应该转化到长整型。

val U = 100000L // 数值上界 + 1

压缩：val key = x * U + y

还原：val x = (key / U).toInt()
val y = (key % U).toInt()

至此，咱们能够应用奢侈 Dijkstra 算法模仿问题。

是否有优化空间？

奢侈 Dijkstra 的每轮迭代中须要遍历 n 个节点寻找候选集中的最短路长度。事实上，这 n 个节点中有局部是“确定集”，有局部是远离终点的边缘节点，每一轮都遍历显得没有必要。咱们应用小顶堆记录候选集中最近深度的节点。不过，这道题是浓密图，奢侈 Dijkstra 优于 Dijkstra + 最小堆。

持续开掘三角不等式性质：

因为间断走两次曼哈顿间隔没有意义，那咱们甚至不须要把非凡门路的终点思考到图中，或者说间接能够应用 specialRoads 数组，而不须要建图的步骤。

6、答疑

• 这道题的数据范畴到 10^5，而非凡门路最多只有 200 条，不是应该算稠密图？

这个观点混同了浓密图的定义，浓密或稠密取决于边数绝对于节点数的大小。简略来说，在节点数固定的状况下，边数越大则图越浓密。在这道题中，每个节点都存在到其余所有节点的门路，因而不仅是浓密图，甚至是齐全图。

题解一（奢侈 Dijkstra）

• 应用 Dijkstra 算法解决最短路问题。

class Solution {fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {
        // 单源正权最短路
        val U = 100001L // 数值上界 + 1
        val INF = 0x3F3F3F3F

        val startL = start[0] * U + start[1]
        val targetL = target[0] * U + target[1]

        if (startL == targetL) return 0
        
        // 1、节点与最短路长度
        val nodes = HashMap<Long, Int>()
        // 1.1 非凡门路上的节点
        for (road in specialRoads) {
            // 过滤无意义的非凡门路（门路破费大于曼哈顿间隔）nodes[road[0] * U + road[1]] = INF
            nodes[road[2] * U + road[3]] = INF
        }
        // 1.2 终点节点与起点节点
        nodes[targetL] = INF
        nodes[startL] = 0 // 终点可能为起点，如果结尾不做特判须要留神程序
        // 2、建有向图（邻接表）<from -> <to -> cost>>
        val graph = HashMap<Long, HashMap<Long, Int>>()
        // 2.1 节点之间的门路（双向边）for ((from, _) in nodes) {graph[from] = HashMap<Long, Int>()
            val fromX = (from / U).toInt()
            val fromY = (from % U).toInt()
            for ((to, _) in nodes) {if (from == to) continue
                val toX = (to / U).toInt()
                val toY = (to % U).toInt()
                graph[from]!![to] = Math.abs(toX - fromX) + Math.abs(toY - fromY)
            }
        }
        // 2.2 非凡门路（单向边）for (road in specialRoads) {val from = road[0] * U + road[1]
            val to = road[2] * U + road[3]
            graph[from]!![to] = Math.min(graph[from]!!.getOrDefault(to, INF), road[4]) // 非凡门路的破费可能更长
        }
        // 3、拜访标记
        val visit = HashSet<Long>()
        // 4、奢侈 Dijkstra
        while (true) {
            // 寻找候选集中最短路长度最短的节点
            var minNode = -1L
            var minDis = -1
            for ((to, dis) in nodes) {if (visit.contains(to)) continue
                if (minDis == -1 || dis < minDis) {
                    minDis = dis
                    minNode = to
                }
            }
            // println("minNode=$minNode, minDis=$minDis")
            // 找到指标点的最短路长度
            if (minNode == targetL) return minDis
            // 拜访标记
            visit.add(minNode)
            // 松弛相邻节点
            for ((to, cost) in graph[minNode]!!) {// println("to=$to, cost=$cost")
                if (minDis + cost < nodes[to]!!) {nodes[to] = minDis + cost
                }
            }
        }
        return -1 // 必然有解
    }
}

复杂度剖析：

• 工夫复杂度：$O(n^2)$ 其中 n 是 specialRoads 非凡门路数组的长度；
• 空间复杂度：$O(n^2)$ 图空间 + 标记数组空间。

题解二（Dijkstra 优化）

• 优化：剪去图空间。

class Solution {fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {
        // 单源正权最短路
        val U = 100001L // 数值上界 + 1
        val INF = 0x3F3F3F3F

        val startL = start[0] * U + start[1]
        val targetL = target[0] * U + target[1]

        if (startL == targetL) return 0

        // 1、节点与最短路长度
        val nodes = HashMap<Long, Int>()
        // 终点节点与起点节点
        nodes[targetL] = INF
        nodes[startL] = 0 // 终点可能为起点，如果结尾不做特判须要留神程序
        // 2、拜访标记
        val visit = HashSet<Long>()
        // 3、奢侈 Dijkstra
        while (true) {
            // 寻找候选集中最短路长度最短的节点
            var minNode = -1L
            var minDis = -1
            for ((to, dis) in nodes) {if (visit.contains(to)) continue
                if (minDis == -1 || dis < minDis) {
                    minDis = dis
                    minNode = to
                }
            }
            // println("minNode=$minNode, minDis=$minDis")
            // 找到指标点的最短路长度
            if (minNode == targetL) return minDis
            // 拜访标记
            visit.add(minNode)
            val minNodeX = (minNode / U).toInt()
            val minNodeY = (minNode % U).toInt()
            // 1、间接到起点
            nodes[targetL] = Math.min(nodes[targetL]!!, minDis + Math.min(nodes[targetL]!!, (target[1] - minNodeY) + (target[0] - minNodeX)))
            // 2、先通过非凡门路（minNode -> 非凡门路的终点 -> 非凡门路的起点）for (road in specialRoads) {val specialTo = road[2] * U + road[3]
                if (specialTo == minNode) continue // 反复门路
                val specialDis = minDis + Math.abs(road[0] - minNodeX) + Math.abs(road[1] - minNodeY) + road[4]
                if (specialDis < nodes.getOrDefault(specialTo, INF)) {nodes[specialTo] = specialDis
                }
            }
        }
        return -1 // 必然有解
    }
}

复杂度剖析：

• 工夫复杂度：$O(n^2)$ 其中 n 是 specialRoads 非凡门路数组的长度；
• 空间复杂度：$O(n)$ 标记数组空间。

题解三（Dijkstra + 最小堆）

附赠一份 Dijkstra + 最小堆的代码：

class Solution {fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {
        // 单源正权最短路
        val U = 100000L // 数值上界 + 1
        val INF = 0x3F3F3F3F

        val startL = start[0] * U + start[1]
        val targetL = target[0] * U + target[1]

        if (startL == targetL) return 0

        // 1、节点与最短路长度
        val nodes = HashMap<Long, Int>()
        // 终点节点与起点节点
        nodes[targetL] = INF
        nodes[startL] = 0 // 终点可能为起点，如果结尾不做特判须要留神程序
        // 2、最小堆
        val heap = PriorityQueue<Long>() { l1, l2 ->
            nodes.getOrDefault(l1, INF) - nodes.getOrDefault(l2, INF)
        }
        heap.offer(startL)
        heap.offer(targetL)
        // 3、Dijkstra
        while (!heap.isEmpty()) {
            // 候选集中最短路长度最短的节点
            val minNode = heap.poll()
            val minDis = nodes[minNode]!!
            // println("minNode=$minNode, minDis=$minDis")
            // 找到指标点的最短路长度
            if (minNode == targetL) return minDis
            val minNodeX = (minNode / U).toInt()
            val minNodeY = (minNode % U).toInt()
            // 1、间接到起点
            val newDirectToTarget = minDis + Math.min(nodes[targetL]!!, (target[1] - minNodeY) + (target[0] - minNodeX))
            if (newDirectToTarget < nodes[targetL]!!) {nodes[targetL] = newDirectToTarget
                heap.offer(targetL)
            }
            // 2、先通过非凡门路（minNode -> 非凡门路的终点 -> 非凡门路的起点）for (road in specialRoads) {val specialTo = road[2] * U + road[3]
                if (specialTo == minNode) continue // 反复门路
                val specialDis = minDis + Math.abs(road[0] - minNodeX) + Math.abs(road[1] - minNodeY) + road[4]
                if (specialDis < nodes.getOrDefault(specialTo, INF)) {nodes[specialTo] = specialDis
                    heap.offer(specialTo)
                }
            }
        }
        return -1 // 必然有解
    }
}

复杂度剖析：

• 工夫复杂度：$O(m·lgn)$ 其中 n 是 specialRoads 非凡门路数组的长度，m 是边数，因为这道题是齐全图，所以有 m = n^2；
• 空间复杂度：$O(n)$ 标记数组空间。

近期周赛最短路问题：

• 2612. 起码翻转操作数（Hard）
• 2608. 图中的最短环（Hard）
• 2577. 在网格图中拜访一个格子的起码工夫（Hard）

Q4. 字典序最小的漂亮字符串（Hard）

https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/

题目形容

如果一个字符串满足以下条件，则称其为 漂亮字符串：

• 它由英语小写字母表的前 k 个字母组成。
• 它不蕴含任何长度为 2 或更长的回文子字符串。

给你一个长度为 n 的漂亮字符串 s 和一个正整数 k。

请你找出并返回一个长度为 n 的漂亮字符串，该字符串还满足：在字典序大于 s 的所有漂亮字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。

对于长度雷同的两个字符串 a 和 b，如果字符串 a 在与字符串 b 不同的第一个地位上的字符字典序更大，则字符串 a 的字典序大于字符串 b。

• 例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个地位（第四个字符）上 d 的字典序大于 c。

示例 1：

输出：s = "abcz", k = 26
输入："abda"
解释：字符串 "abda" 既是漂亮字符串，又满足字典序大于 "abcz"。能够证实不存在字符串同时满足字典序大于 "abcz"、漂亮字符串、字典序小于 "abda" 这三个条件。

示例 2：

输出：s = "dc", k = 4
输入：""解释：能够证实，不存在既是漂亮字符串，又字典序大于"dc" 的字符串。

提醒：

• 1 <= n == s.length <= 105
• 4 <= k <= 26
• s 是一个漂亮字符串

问题结构化

1、概括问题指标

结构一个满足条件的指标字符串，命名为「漂亮字符串」。

2、剖析问题要件

• 字符集：题目要求指标字符串仅能应用小写字母表的前 k 个字母，例如 k = 4 只能应用 {a, b, c, d}；
• 漂亮字符串（限度回文）：题目要求指标字符串不蕴含长度大于 1 的回文子串；
• 字典序更大：题目要求指标字符串的字典序大于字符串 s；
• 字典序最小：题目要求返回字典序最小的计划；

3、察看数据特色

• 数据量：数据量的上界是 10^5，这要求算法的工夫复杂度不能高于 O(n^2)；
• 输出字符串 s 自身就是「漂亮字符串」。

4、察看测试用例

以 s =“abcz”, k = 26 为例：

• 批改‘z’：无奈批改’z’取得字典序更高的字母；
• 批改‘c’：能够批改‘c’为’d’失去“abdz”，且形成「漂亮字符串」；
• 批改‘a’或’b’：也能够结构「漂亮字符串」，但字典序不会优于“abdz”。

5、进步形象水平

• 权重：字典序的规定中，字符串越靠前的地位对排序的影响权重越大，例如序列”ba“的字典序大于”az“；
• 晋升：为了结构字典序更大的「漂亮字符串」，咱们须要将字符串中的某个字母批改为字母序更大的字母，例如将‘a’晋升到‘b’或‘z’；
• 下一个排列：题目要求指标字符串的字典序大于字符串 s，又是所有计划中字典序最小的，问题模型相似经典题目「31. 下一个排列」，能够借鉴；
• 是否为决策问题：因为每次晋升操作有多种地位抉择，因而这是个决策问题，精确来说是一个结构问题。
• 总结：这是一个结构问题，要求结构满足条件的「下一个漂亮字符串」。

6、具体化解决伎俩

如何结构满足条件的「下一个漂亮字符串」？

因为题目要求结构字典序最小的计划，那么将 s[i] 晋升为字母序更大的下一个字母是最优的，例如将’a’晋升到‘b’优于晋升到‘z’。除非在 s[i] 曾经是字典序最大的字母‘z’时，咱们须要晋升它的前一个字母 s[i – 1]，例如将”az“晋升为”bz“优于“cz”。

结构「下一个漂亮字符串」须要晋升字母序，那么如何决策替换策略？

因为字符串中越靠前的地位的权重越高，容易想到的贪婪策略是从后往前晋升字符。如果晋升 s[n – 1] 可能结构「漂亮字符串」，那么间接晋升 s[n – 1] 即可，否则须要晋升更靠前的 s[n – 2]。

当咱们确定晋升 s[i] 的有效性后，持续向前晋升没有意义，而因为 s[i] 的字母序自身曾经更大了，且 s[i] 的权重在 [i, n) 区间里是最高的，因而前面不管怎么填字典序都是更大的。那么，为了取得字典序最小的「下一个漂亮字符串」，咱们能够贪婪地将后续字符升高到字母序最低的字母，例如”abcz“晋升到”abdz”后，将‘z’升高到‘a’。

这个思考过程，与「下一个排列」问题是比拟类似的。在「下一个排列」问题中，咱们替换尽可能靠后的一个正序对，因为剩下的序列不管怎么填都是更大的排列，所以咱们间接对后续字母做正序排列能够失去最小的字典序。

如何验证晋升的有效性（晋升字母序后会可能引入新的回文信息）？

在「察看数据特色」中得悉，输出字符串 s 自身就是「漂亮字符串」，而且咱们是从后向前晋升字符，那么晋升 s[i] 只可能结构出长度为 2 或长度为 3 的回文子串，咱们须要以 i 为核心向左右扩大，验证是否有回文串信息。联合上一个问题，因为咱们在晋升 s[i] 后还须要升高后序地位的字母序，所以咱们只须要向右边扩大验证有效性。

至此，咱们能够确定整体框架，分为 2 个阶段：

阶段一：晋升 s[n - 1]
while (i 从后往前遍历) {for (c in s[i] + 1 until 'a' + k) { // 枚举字符集
                if (存在回文信息) continue
                s[i] = c // 确定有效性
                // 记录下标 i
        }
        // 无奈晋升 s[i]，尝试晋升 s[i - 1]
}

阶段二：// 将 [i + 1, n) 升高为最小字符
for(j in i + 1 until n) {for (c in 'a' until 'a' + k) { // 枚举字符集
                if (存在回文信息）continue
                s[j] = c
                break
        }
}

答疑：

• 为什么阶段二没有解决无奈结构的状况？

因为题目提醒 k 的取值范畴是大于等于 4 的，也就是字符集的大小最小为 4，而验证「有效性」只须要察看地位 i 的前两个地位。那么在长度为 3 的子区间 [i-2, i] 中，咱们总可能从大小为 4 的字符集中，抉择出一个不会结构出回文信息的子串。因而，阶段二是必然可结构的。甚至来说，题目将 k 的取值范畴批改到 [3, 26]，咱们的算法也是成立的。

题解（贪婪）

class Solution {fun smallestBeautifulString(s: String, k: Int): String {
        val n = s.length
        val U = 'a' + k
        val sArray = s.toCharArray()
        var pos = -1
        outer@ for (i in n - 1 downTo 0) {
            // 尝试晋升字母序
            for (c in sArray[i] + 1 until U) {
                // 验证有效性（只须要验证右边）if ((i > 0 && c == sArray[i - 1]) || (i > 1 && c == sArray[i - 2])) continue
                sArray[i] = c
                pos = i
                break@outer
            }
        }

        // 无奈结构
        if (pos < 0) return ""

        for (i in pos + 1 until n) {for (c in 'a' until U) {
                // 验证有效性（只须要验证右边）if ((i > 0 && c == sArray[i - 1]) || (i > 1 && c == sArray[i - 2])) continue
                sArray[i] = c
                break
            }
        }

        return String(sArray)
    }
}

复杂度剖析：

• 工夫复杂度：$O(n)$ 其中 n 为字符串 s 的长度，每个地位最多被拜访 2 次，而每个地位的晋升操作最多执行 2 次，升高操作最多执行 2 次；
• 空间复杂度：$O(1)$ 不思考后果数组。

类似问题：

• 31. 下一个排列
• 647. 回文子串