最长有序元音完整子序列：O(n²) DP算法的优化问询

当然有更高效的解法！你的O(n²)动态规划思路虽然正确，但可以利用元音数量固定（仅5个）的特性，将时间复杂度降到O(n)，空间复杂度压缩到O(1)。

核心思路 #

我们不需要为每个字符维护DP状态，只需要用一个长度为5的数组记录以每个元音结尾的最长符合要求子序列的长度，数组索引对应顺序：0→a、1→e、2→i、3→o、4→u。

遍历字符串时，针对每个元音字符做如下更新：

• 如果是a：直接将对应索引的长度加1，每个新的a都能延长以a结尾的子序列。
• 如果是其他元音：当前元音的最长子序列长度 = max(当前元音的已有长度, 前一个元音的最长长度) + 1。这是因为当前元音既可以接在同类型元音后面（允许重复），也可以接在前一个顺序的元音后面，取两种情况的最大值再加1即可。

最终结果就是以u结尾的最长子序列长度，若该值为0则返回0（说明无法形成到u的有效完整子序列）。

代码实现 #

def find_longest_vowel_subsequence(vowels):
    # dp数组对应a、e、i、o、u的最长子序列长度
    dp = [0] * 5
    vowel_map = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
    
    for c in vowels:
        idx = vowel_map[c]
        if idx == 0:
            dp[idx] += 1
        else:
            dp[idx] = max(dp[idx], dp[idx-1]) + 1
    
    return dp[4] if dp[4] != 0 else 0

效果对比 #

• 原解法：时间O(n²)，空间O(n)，在字符串长度较大时（比如n=10^5）会出现明显性能瓶颈。
• 优化解法：时间O(n)，空间O(1)，无论字符串多长都能高效处理。

测试验证 #

• 输入"aeiaeiou"，返回6，与示例一致。
• 输入"aeiaaioooaauuaeiou"，返回10，符合预期。
• 输入"aaaaa"，返回0（无有效到u的子序列）。
• 输入"aeiou"，返回5，正确。

内容的提问来源于stack exchange，提问作者John Doe