LeetCode 补充题 134. 固定长度数字子串的最大值
题目描述
牛客原题： ✅ 补充题 134. 固定长度数字子串的最大值
给你一个只包含数字
1到9的字符串s和一个整数k，请从中选择一个长度为k的连续子串，使它表示的十进制整数最大。本文以字符串形式返回这个最大整数，避免受到平台整数宽度的限制；牛客原题接口返回整数，数值含义相同。
示例 1：
输入：
s = "321", k = 2
输出："32"
解释： 候选子串为 "32"、"21"，前者表示的整数更大。
提示：
- 字符串只含数字
1…9。 -
1≤k≤字符串长度。 - 选择的字符必须连续。
- 结果以十进制字符串返回。
题意分析
所有候选都是长度为
k的数字串，第一次不同的位置上数字越大，整段数值就越大。因此可以直接按字符比较，既不需要转换大整数，也不会因平台整数宽度限制失真。
解法：比较固定长度窗口的字典序
核心思路
[!blue]
用
best保存已扫描窗口中的最优起点。依次枚举满足i + k <= n的其他起点，将当前窗口与best从第一个字符开始比较，跳过相同前缀。若在第
j位首次不同，只在新窗口该位更大时更新best；若k位全部相同，两者结果一致，保留原起点即可。每轮后best仍然对应已枚举候选的最大值，扫描完即得到全局最优。比较阶段只保存下标，最后截取一次结果。
k == n时只有一个窗口，不进入比较循环；长公共前缀可能使每次比较花费O(k)，不能把该实现误写成线性时间。
解题步骤
- 记录当前最优窗口起点，初始为 0。
- 逐个枚举其他合法起点，从头比较最多 k 个字符，首次不同处决定优劣。
- 全部窗口比较后，只构造一次最终长度为 k 的结果。
代码实现
class Solution {
public String largestWindow(String s, int k) {
if (k <= 0 || k > s.length()) {
throw new IllegalArgumentException("invalid length");
}
int best = 0;
for (int i = 1; i + k <= s.length(); i++) {
int j = 0;
while (j < k && s.charAt(best + j) == s.charAt(i + j)) {
j++;
}
if (j < k && s.charAt(i + j) > s.charAt(best + j)) {
best = i;
}
}
return s.substring(best, best + k);
}
}
func largestWindow(s string, k int) string {
if k <= 0 || k > len(s) {
panic("invalid length")
}
best := 0
for i := 1; i+k <= len(s); i++ {
j := 0
for j < k && s[best+j] == s[i+j] {
j++
}
if j < k && s[i+j] > s[best+j] {
best = i
}
}
return s[best : best+k]
}
复杂度分析
- 时间复杂度：$O(nk)$。
- 空间复杂度：额外工作空间 $O(1)$，返回结果占O(k)。
关键点总结
[!green]
等长数字串的数值顺序与字典序一致，直接比较字符即可避免大整数溢出；最坏仍需 $O(nk)$ 比较。
易错点总结
[!yellow]
没有将大数字强制转int；本解没有声称线性时间。原题未列明确复杂度目标，若另外要求线性时间，应另选字符串后缀算法。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1163. 按字典序排在最后的子串 | 困难 | 可学习跳过不优起点的后缀比较方法；本题还限制长度 k，不能直接返回不足 k 长度的最大后缀。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！