LeetCode 1446. 连续字符
题目描述
题意分析
寻找字符串中最长的一段连续相同字符，返回这一段的长度。字符必须相邻，中间被其他字符隔开后就属于不同段，不能把同一个字母在全串中的出现次数相加。
答案只关心段长，不需要返回具体字符或区间。题目保证字符串非空，因此至少有一个长度为一的合法段；如果所有相邻字符都不同，答案就是一。
解法：一次扫描连续段
核心思路
[!blue]
用
cur表示以当前下标结尾的同字符连续段长度，用maxLen保存目前发现的最大段长。这里cur只描述当前末尾，字符一旦改变就不能再继承前一段的长度。处理新字符时，只需与紧邻的前一个字符比较。相同则它接在同一连续段后面，令
cur加一；不同则旧段已经结束，当前字符自己形成一个新段，长度从一开始。这个局部判断足以确定当前同字符后缀，不必回头扫描整段。每处理一个位置就用
cur更新maxLen。任意连续段在它的最后一个位置达到完整长度，此时必然被纳入比较，所以无论最长段位于中间还是字符串末尾都不会漏掉。初始已经处理第零个字符，两个长度都设为一，循环从下标一开始。单字符输入不进入循环，直接返回一，也符合定义。
解题步骤
- 初始化
cur = 1、maxLen = 1，表示已经处理首字符。- 从下标一开始，比较当前字符与前一个字符。
- 相同则增加
cur，不同则将cur重置为一。- 每轮用
cur更新maxLen，最后返回全局最大长度。
代码实现
class Solution {
public int maxPower(String s) {
// cur：以当前下标结尾的同字符连续段长度；题目保证 s 非空，故初值取 1。
int maxLen = 1;
int cur = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
cur++;
} else {
// 新段从 i 自己开始，长度是 1 而不是 0。
cur = 1;
}
// 每个位置都结算一次，末尾那段无需循环外补算。
maxLen = Math.max(maxLen, cur);
}
return maxLen;
}
}
func maxPower(s string) int {
// cur：以当前下标结尾的同字符连续段长度；题目保证 s 非空，故初值取 1。
maxLen := 1
cur := 1
for i := 1; i < len(s); i++ {
if s[i] == s[i-1] {
cur++
} else {
// 新段从 i 自己开始，长度是 1 而不是 0。
cur = 1
}
// 每个位置都结算一次，末尾那段无需循环外补算。
if cur > maxLen {
maxLen = cur
}
}
return maxLen
}
复杂度分析
- 时间复杂度：
O(n)。每个字符只与前一个字符比较一次。- 空间复杂度：
O(1)。只维护当前连续段长度与历史最大长度。
关键点总结
[!green]
- 当前段长度取决于相邻字符关系，不是字符总频次。
- 新段包含当前字符，因此重置为一。
- 逐位置更新最大值，能统一覆盖所有段和末尾边界。
易错点总结
[!yellow]
- 字符变化后重置为零：当前字符已经属于新段，会少计算一个字符。
- 只在字符变化时结算：最后一段后面没有新字符触发变化，可能漏掉末尾答案。
- 返回
cur：它仅表示最后一段，最长段可能出现在前面。- 使用频次数组累加相同字符：会把被其他字符隔开的多个段合并，不满足连续要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 485. 最大连续 1 的个数 | 简单 | 把连续1扩展为连续相同字符，遇到字符变化时重置当前段长度。 |
| 443. 压缩字符串 | 中等 | 同样按游程处理重复字符，本题只保留最长段长度，原题输出每段编码。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！