题目描述
思路解析动画文字版
记牢两步:先全填 a 拿最小底盘;再从最后一位往前把要补的值铺成 z,剩的零头加到中间一位。下面每帧都在套这两步。
总览 · 六个空位要填,数值要凑到 80：上面这排六个占位点,就是要拼的六位串,现在一位都没填。右边账本记三样:目标数值 k 是 80,当前已凑到的数值,还有两者的差,也就是还要补多少。接下来先把每一位都铺成最小的 a。
铺底盘 · 第 0 位放最小的 a：把第 0 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 1。先全用 a,既保证左边字典序最小,数值也从最小起步。
铺底盘 · 第 1 位放最小的 a：把第 1 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 2。先全用 a,既保证左边字典序最小,数值也从最小起步。
铺底盘 · 第 2 位放最小的 a：把第 2 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 3。先全用 a,既保证左边字典序最小,数值也从最小起步。
铺底盘 · 第 3 位放最小的 a：把第 3 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 4。先全用 a,既保证左边字典序最小,数值也从最小起步。
铺底盘 · 第 4 位放最小的 a：把第 4 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 5。先全用 a,既保证左边字典序最小,数值也从最小起步。
铺底盘 · 第 5 位放最小的 a：把第 5 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 6。先全用 a,既保证左边字典序最小,数值也从最小起步。
底盘成形 · 全 a 是字典序最小的起点：六位现在全是 a,串是 "aaaaaa",数值是 6。这是字典序能给到的最小底盘。但目标数值是 80,眼下只有 6,还差一大截,下面要把缺口补上。
算缺口 · 还差 74 点要补回去：目标 80 减去底盘 6,得到缺口 74。这 74 点就是要靠把某些 a 换成更大的字母补回来的量。问题只剩一个:这些增大放在哪几位最划算。
定方向 · 增大全推到最右边：字典序是从左往右比的,越靠左越想留小字母 a。所以把增大数值这件事尽量推到最右边,从最后一位也就是第 5 位开始动手。指针先停在第 5 位上。
第 5 位 · 剩的够铺一个满 z：看第 5 位。现在还要补 74 点,比 25 多,说明这一位可以从 a 直接顶到 z。a 到 z 差 25,顶上去正好吃掉 25 点缺口,把最大的增量压在这个靠右的位置最省字典序。
第 5 位 · 改成 z,缺口减 25：把第 5 位从 a 改成 z,蓝色标出来的就是已经铺好的 z。缺口从 74 减到 49。串现在是 "aaaaaz"。接着往左挪一位,看还要不要继续铺。
第 4 位 · 剩的够铺一个满 z：看第 4 位。现在还要补 49 点,比 25 多,说明这一位可以从 a 直接顶到 z。a 到 z 差 25,顶上去正好吃掉 25 点缺口,把最大的增量压在这个靠右的位置最省字典序。
第 4 位 · 改成 z,缺口减 25：把第 4 位从 a 改成 z,蓝色标出来的就是已经铺好的 z。缺口从 49 减到 24。串现在是 "aaaazz"。接着往左挪一位,看还要不要继续铺。
第 3 位 · 剩的不够再铺满 z：挪到第 3 位,现在只剩 24 点要补,不够再铺一个满 z 了。所以铺 z 的过程到此为止,剩下这点零头要一次性加到当前这一位上。
第 3 位 · 用一位吸收零头：这第 3 位就是中间那个调整字符。把剩下的 24 点加到它头上,也就是从 a 往后数 24 个字母。零头只有一份,所以这种调整位至多一个,它左边全是 a、右边全是 z。
第 3 位 · 定成 y,缺口归零：a 往后数 24 个字母,落在 y 上,把第 3 位定成 y。缺口正好清零。现在串是 "aaayzz",左边三个 a、中间一个 y、右边两个 z,全部就位。
完成 · 答案串 "aaayzz"：六位全部定下来,串是 "aaayzz",长度正好 6,第一个要求满足。下面再核一遍数值对不对、字典序是不是真的最小。
核对数值 · 加起来正好 80：把每位的数值加起来:三个 a 各 1,一个 y 是 25,两个 z 各 26,合起来 1 加 1 加 1 加 25 加 26 加 26,正好是 80。数值这一关也对上了。
核对字典序 · 小字母全在左边：再看字典序:最左边能留的位置全留了最小的 a,不得不增大的 y 和两个 z 全被压到了右边。任何把大字母往左挪的改法都会让字典序变大,所以这就是字典序最小的那个串。
回放 · 先铺 a,再从右铺 z,中间吸零头：整体回放一遍:先把六位都铺成 a 拿到最小底盘,算出还差 74,从最后一位往左把缺口铺成两个 z,剩下的 24 点加到中间一位变成 y。三步走完,得到 "aaayzz",和题目要的答案严丝合缝。
边界:k 等于 n 时全是 a;单位时零头直接加到这一位;k 顶到最大时全填 z,缺口正好被铺满。
面试重点:全填 a 拿最小底盘、增大推到最右;中间调整字符是零头所致、至多一个;全程 O(n) 无排序。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def getSmallestString(self, n: int, k: int) -> str: ans = ['a'] * n i, d = n - 1, k - n while d > 25: ans[i] = 'z' d -= 25 i -= 1 ans[i] = chr(ord(ans[i]) + d) return ''.join(ans)复杂度
- 时间：O(n)，先把 n 位全填 a 是一遍 O(n);再从末尾往前铺 z,每位最多被改一次,也是 O(n) 之内;没有任何排序。两段加起来还是线性的 O(n),n 是字符串长度
- 空间：O(n)，按峰值算,主要是那个长度 n 的字符数组或字符串,占 O(n),它既是中间结果也是最终答案。除它之外只用了 d 和 i 两个变量,是常数 O(1)。所以不计输出本身时辅助空间是 O(1),计入输出则是 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么先把每一位都填成 a,再从后往前改,而不是从前往后凑?
追问中间那个调整字符是怎么冒出来的,为什么至多只有一个?
追问这道题的时间和空间复杂度是多少,需要排序吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
十-二进制数的最少数目
LeetCode 1689 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题