1. 项目概述与核心价值最近在准备华为OD机试的朋友应该对“非严格递增连续数字序列”这道题不陌生。它频繁出现在D卷的真题库里分值不低通常占100分属于那种思路清晰但细节坑多的题目。很多人在第一次遇到时要么被“非严格递增”这个条件绕晕要么在边界处理和效率优化上栽跟头。我当年备考时也在这道题上卡过壳后来经过反复琢磨和实战总结出了一套稳定且高效的Java解法。今天我就把自己踩过的坑、理清的思路以及最终打磨出来的代码实现毫无保留地分享出来。这篇文章不仅是一份“参考答案”更是一份“解题心法”适合所有正在备战华为OD机试、希望夯实字符串与动态规划或者说双指针滑动窗口基本功的Java开发者。无论你是刚开始刷题的新手还是想寻找更优解法的老手相信都能从中获得直接的启发和可复用的代码。2. 题目深度解析与核心思路拆解2.1 题意理解与关键定义首先我们必须把题目描述翻译成程序员能精准理解的语言。题目通常会给一个字符串字符串中只包含数字‘0’-‘9’和其他字符。我们需要从这个字符串中找出最长的、连续的数字子序列并且这个数字子序列满足“非严格递增”。这里有几个关键词需要咬文嚼字连续的数字子序列这意味着我们找的是一串在原始字符串中位置连续的数字字符中间不能夹杂非数字字符。例如字符串“a123bc45”其中“123”和“45”都是连续的数字子序列而“12345”则不是因为中间被‘b’和‘c’隔开了。非严格递增这是本题的核心难点。“严格递增”要求序列中每个后一位的数字都大于前一位如 1, 2, 3, 4。而“非严格递增”则允许后一位数字大于或等于前一位如 1, 2, 2, 3, 3。这意味着相等的数字是允许连续出现的。所以我们的目标就是扫描整个字符串每当遇到连续的数字段时就判断这个数字段内最长的非严格递增序列有多长最后返回所有数字段中这个长度的最大值。2.2 解题思路演进从暴力到优化最直观的暴力解法是遍历字符串找到每一个连续的数字子串然后对每个子串检查其所有可能的连续子序列是否满足非严格递增。这复杂度太高不可行。我们需要一个在线处理一次遍历的算法。核心思路是双指针或称滑动窗口配合状态记录。主指针遍历用一个指针i从头到尾遍历字符串。识别数字段当i指向的字符是数字时我们进入一个“数字段处理模式”。动态维护当前递增序列这是算法的核心。我们不能简单地遇到数字就累加长度。例如“12321”从‘1’到‘3’都是递增的长度为3但遇到后面的‘2’时它比前一个‘3’小破坏了递增性。然而“非严格递增”序列可以从这里重新开始计算吗注意题目要求是“连续数字序列”所以当遇到递减时当前这个长的递增序列就结束了。但是新的序列可以从这个破坏点开始吗答案是可以但新的序列必须包含这个破坏点。对于“12321”当走到最后一个‘1’时最长的非严格递增序列是“123”长度为3不对实际上“1232”和“12321”都不满足。我们需要的是从某个起点开始一直保持非严格递增到当前点。更精确的算法描述如下我们维护一个currentLength表示以当前遍历到的数字字符为结尾的、满足非严格递增的连续数字序列的长度。同时我们维护一个maxLength记录全局最大值。当我们从位置i移动到i1且两者都是数字时如果str[i1] str[i]那么当前这个递增序列可以延续currentLength。如果str[i1] str[i]那么以str[i]结尾的递增序列无法再包含str[i1]了。但是一个新的递增序列可以从str[i1]本身开始所以currentLength应该重置为1因为str[i1]自己构成一个长度为1的递增序列。当i指向非数字字符时说明当前连续数字段中断了我们需要将currentLength重置为0并准备开始下一个数字段。这个思路本质上是一种简化的动态规划其状态定义就是“以当前字符结尾的最长非严格递增数字序列长度”。注意这里有一个极其关键的边界情况也是很多人第一次写会出错的地方数字字符的转换。我们比较的是数字字符的ASCII码还是数字本身的大小例如字符‘9’的ASCII码是57字符‘10’不存在但‘1’和‘0’是两个字符。我们比较的是相邻数字字符所代表的数值。‘2’ ‘1’在ASCII码和数值上都是成立的但‘10’ ‘9’吗不我们是逐字符比较所以是‘1’和‘9’比较显然‘1’ ‘9’。因此直接比较字符是可行的因为数字字符‘0’-‘9’的ASCII码是连续递增的字符比较等价于数值比较。这是一个重要的简化。2.3 方案选型与优势为什么选择这种“单次遍历状态维护”的方法时间复杂度 O(n)只需遍历字符串一次在处理大规模输入时效率极高完全满足机试的时限要求。空间复杂度 O(1)只使用了几个整型变量作为状态记录无需额外数组内存消耗极小。逻辑清晰将复杂问题分解为“识别数字段”和“段内求最长非严格递增子序列”两个子问题并通过一个状态变量currentLength巧妙地将后者融合在一次遍历中解决避免了复杂的二维动态规划。3. 核心代码实现与逐行解析理解了思路我们来看代码。我会提供一份健壮、注释清晰的Java实现并逐行解释其意图和注意事项。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String input scanner.nextLine(); scanner.close(); int maxLen 0; // 全局最长长度 int currentLen 0; // 当前连续数字序列中以当前位置结尾的非严格递增序列长度 char prevChar ; // 记录前一个字符初始化为非数字 for (int i 0; i input.length(); i) { char c input.charAt(i); if (Character.isDigit(c)) { // 当前字符是数字 if (currentLen 0) { // 情况1当前是数字段的第一个数字序列长度初始为1 currentLen 1; } else if (c prevChar) { // 情况2当前数字 前一个数字满足非严格递增长度1 currentLen; } else { // 情况3当前数字 前一个数字破坏了递增性。 // 注意此时新的递增序列可以从当前数字重新开始长度为1。 // 但是我们需要先更新全局最大值吗不在重置currentLen之前它保存的是之前那个递增序列的长度。 // 所以先更新maxLen。 maxLen Math.max(maxLen, currentLen); currentLen 1; // 重新开始以当前字符为起点长度为1 } // 更新全局最大值这里也包含了情况1和情况2中当前递增序列可能是最长的情况 maxLen Math.max(maxLen, currentLen); prevChar c; // 更新前一个字符为当前数字字符 } else { // 当前字符不是数字数字段中断 // 在中断前currentLen保存的是上一个数字段内最后一个递增序列的长度需要用它更新maxLen maxLen Math.max(maxLen, currentLen); currentLen 0; // 重置当前长度准备下一个数字段 prevChar ; // 重置前一个字符为非数字这样下一个数字到来时会触发“情况1” } } // 循环结束后还需要再检查一次因为字符串可能以数字结尾 maxLen Math.max(maxLen, currentLen); System.out.println(maxLen); } }3.1 代码关键点解析字符判断使用Character.isDigit(c)来判断是否为数字这比c 0 c 9更简洁且不易出错特别是考虑到代码可读性。状态变量currentLen的含义它不是当前连续数字段的长度而是当前连续数字段内以当前位置结尾的、满足非严格递增条件的子序列长度。这是理解整个算法的钥匙。prevChar的初始化与重置初始化为非数字如空格‘ ’这样遇到第一个数字时currentLen0的条件会触发正确初始化长度为1。当遇到非数字字符时除了重置currentLen也必须重置prevChar否则下一个数字段会错误地使用上一个数字段的最后一个数字进行比较。更新maxLen的时机在currentLen增长时情况1和情况2的循环末尾。在currentLen因递减而需要重置前情况3的开头。这是最容易遗漏的点如果不在这里更新像“121”这样的序列最大长度是2“12”但当你走到最后一个‘1’时currentLen从2变为1如果不在变化前保存2这个最大值就会丢失。在数字段结束时遇到非数字字符时。在整个字符串遍历结束后。这是第二个容易遗漏的点如果字符串以数字结尾最后一个数字段的信息还在currentLen里必须在循环外再次更新maxLen。非严格递增的判断c prevChar直接使用字符比较简洁有效。3.2 测试用例与验证让我们用几个典型用例跑一下这个算法验证其正确性输入字符串预期输出分析过程abc12345def5数字段“12345”完全递增长度为5。a1123b0011c4数字段“1123”中“1123”满足非严格递增长度为4。数字段“0011”也满足长度为4。取最大值4。12321abc3数字段“12321”1(len1) -2(, len2) -3(, len3) -2(, 保存max3, len重置为1) -1(, 保存max3, len重置为1)。最终max3。9a8b7c61每个单独的数字构成一个长度为1的序列。1113全部相等满足非严格递增长度为3。a0b123c321d453数字段“0”长1“123”长3“321”中“32”和“21”都不满足最长是单个字符1“45”长2。最大值3。(空字符串)0初始maxLen0循环不执行最终输出0。abcdef0没有数字currentLen始终为0输出0。4. 常见陷阱与深度调试技巧即使思路正确实现时也可能掉进一些陷阱。下面是我在多次练习和帮别人调试中总结出的高频问题。4.1 陷阱一混淆“连续数字段”和“非严格递增序列”错误表现没有在遇到非数字时重置状态导致将两个分离的数字段错误地连在一起判断。例如输入“123ab45”错误输出5认为“12345”正确输出应为3“123”。排查方法在循环内打印日志。在else分支遇到非数字和重置currentLen、prevChar的地方打印一条调试信息观察状态是否被正确清空。// 调试代码片段 else { System.out.println(“[DEBUG] 遇到非数字 ‘“ c “‘ 重置状态。当前maxLen” maxLen); maxLen Math.max(maxLen, currentLen); currentLen 0; prevChar ‘ ’; }4.2 陷阱二更新maxLen的时机遗漏错误表现对于“121”这样的输入输出2正确应为2但算法可能输出1。问题就出在currentLen从2变为1时没有在重置前用2去更新maxLen。解决方案严格遵循上一节提到的四个更新maxLen的时机。可以画一个状态迁移图来帮助记忆每当currentLen发生可能丢失历史最大值的变化前由大变小或段结束就必须更新maxLen。4.3 陷阱三prevChar初始化与重置问题错误表现输入“a123”结果可能出错。因为第一个数字‘1’的前一个字符prevChar初始值如果是数字比如‘0’那么‘1’ ‘0’成立currentLen会被计算为2这显然是错的。解决方案确保prevChar的初始值是一个非数字字符并且在每个数字段结束时遇到非数字后将其重置为非数字字符。这样每个数字段的第一个数字都会正确地触发currentLen1的初始化逻辑。4.4 性能与边界考量大字符串输入本题解法是O(n)时间O(1)空间可以轻松处理长达10^5甚至10^6的字符串。机试环境通常无忧。输入格式题目通常明确说明字符串中可能包含大小写字母和数字。我们的Character.isDigit()方法兼容性很好。最大长度定义题目要求输出一个整数即长度。我们的maxLen用int存储足够。如果理论长度可能超过Integer.MAX_VALUE那输入字符串本身会巨大到不现实。5. 思路拓展与变种题目掌握了这道题的核心——在连续数字段内维护以当前字符结尾的最长非严格递增子序列长度你可以解决一系列变种问题。5.1 变种一严格递增连续数字序列如果题目改成“严格递增”只需要将判断条件c prevChar改为c prevChar。这是最简单的变种。5.2 变种二非严格递增连续字符序列不限数字如果字符串包含任意字符如字母要求找出最长的非严格递增按ASCII码连续字母序列。解法完全一样只需将判断Character.isDigit(c)改为Character.isLetter(c)即可。5.3 变种三返回序列本身而不仅仅是长度这是一个常见的进阶要求。我们需要在维护长度的同时记录这个最长序列的起始和结束索引。修改思路新增变量startIndex和endIndex记录全局最长序列的起止位置。在currentLen变化时我们需要知道当前这个递增序列的起点。可以新增一个currentStart变量表示当前递增序列的起始索引。当currentLen被重置为1时即遇到数字段第一个数字或发生递减currentStart更新为当前索引i。当currentLen增加时currentStart保持不变。每当更新maxLen时如果新的maxLen比旧的大就同时更新startIndex和endIndex为currentStart和i。最后使用input.substring(startIndex, endIndex 1)即可得到最长序列字符串。这个变种练习能帮你更深刻地理解状态currentLen和序列起点的对应关系。5.4 变种四允许最多修改一个字符或删除/增加一个字符这类问题难度上一个台阶通常需要更复杂的动态规划DP或双指针配合计数。例如“给定一个数字字符串你可以将其中的一个字符修改为任意数字求能得到的最长非严格递增连续数字序列的长度”。这需要维护“未修改状态下的长度”和“已修改一次状态下的长度”两个状态。这已经超出了本题的简单双指针范畴属于动态规划的经典题型备考华为OD更高难度的题目可能会遇到。6. 华为OD机试实战技巧最后结合华为OD的考试环境分享几个针对性技巧输入处理华为OD的Java题目通常使用Scanner或BufferedReader读取输入。对于字符串题目Scanner.nextLine()是最常用的。务必注意如果题目说明是“有多组测试用例”则需要使用while (scanner.hasNextLine())循环读取。本题通常是单用例。类名与方法机试环境通常要求类名为Main并且包含public static void main(String[] args)方法。不要画蛇添足创建其他不必要的类或方法。效率与简洁在保证正确性的前提下代码应尽量简洁、高效。避免使用复杂的集合类如ArrayList来存储中间结果本题用几个基本变量足矣。像我们上面提供的解法就是考场上的“标准答案”风格。调试机试环境可能不支持单步调试但支持打印。在无法确定逻辑时可以在关键分支打印变量值如currentLen,maxLen,prevChar但提交前务必注释或删除所有调试输出否则可能因输出格式不符而判错。自测写完代码后务必用上面提供的测试用例以及你能想到的边界情况空串、全数字、全非数字、交替出现、长串等自己跑一遍。逻辑严密性是通过大量练习和自测培养出来的。这道“非严格递增连续数字序列”题完美考察了选手对字符串处理、状态机思想以及边界条件的把控能力。吃透它不仅是为了通过某一场考试更是为了夯实解决一大类线性扫描、状态维护问题的基本功。在实际的软件开发中处理日志流、用户行为序列等场景时类似的思路同样适用。希望这份超详细的拆解能帮你彻底拿下这个知识点。如果在练习中遇到其他问题欢迎随时交流。
