leetcode
leetcode 1951 ~ 2000
最大波动的子字符串

最大波动的子字符串

难度:

标签:

题目描述

代码结果

运行时间: 527 ms, 内存: 16.0 MB


/*
 * 题目思路:
 * 使用Java Stream实现需要对每个子字符串计算频率分布,
 * 并找到最大频率和最小频率的差值,返回最大波动值。
 */

import java.util.stream.IntStream;

public class MaxFluctuationStream {
    public int maxFluctuation(String s) {
        return IntStream.range(0, s.length())
            .map(i -> IntStream.range(i, s.length())
                .map(j -> {
                    int[] freq = new int[26];
                    s.substring(i, j + 1).chars().forEach(c -> freq[c - 'a']++);
                    int maxFreq = IntStream.of(freq).max().orElse(0);
                    int minFreq = IntStream.of(freq).filter(f -> f > 0).min().orElse(0);
                    return maxFreq - minFreq;
                })
                .max().orElse(0))
            .max().orElse(0);
    }
}

解释

方法:

这道题的解决方案使用了双层字母频率差分数组来跟踪任意两个字符的出现次数差异。首先,对于全由同一字符构成的字符串,波动值为0。接着,定义两个二维数组,分别用来记录每对字符在遍历过程中的次数差(diff)和含波动性的次数差(diff_with_b)。遍历字符串中的每个字符,并更新两个数组:如果当前字符是i,那么对于所有不等于i的j,增加diff[i][j],减少diff[j][i]。若diff[j][i]变为负值,则重置为0,表示重新开始计算该对字符的差异。同时更新diff_with_b,该数组记录了包含至少一次波动性的最大次数差。最后,遍历完所有字符后,diff_with_b数组中的最大值即为答案。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在这个算法中,为什么需要两个二维数组diff和diff_with_b来分别追踪字符对的次数差和含波动性的次数差?
在这个算法中,数组 `diff` 用于追踪任意两个不同字符之间的出现次数差。这个差值可以帮助我们理解两个字符在任意时间点的相对频率。数组 `diff_with_b` 则用于追踪包含至少一次波动(即一方至少比另一方多出现一次)的次数差的最大值。这种分开追踪的方式允许我们准确地计算出在任何时点字符出现的动态差异,并保持记录在何时某个字符对首次出现波动,这对于解决问题至关重要。
🦆
算法解释中提到,如果diff[j][i]变为负值,则重置为0,并且diff_with_b[i][j]更新为diff[i][j]。这种重置的逻辑是如何帮助我们找到最大波动值的?
当 `diff[j][i]` 变为负值时,意味着在当前的字符序列中,字符 `i` 出现的次数比字符 `j` 更少。重置 `diff[j][i]` 为0是为了重新开始计数这两个字符的差异,忽略之前的负波动。这是因为我们只对正的波动值感兴趣(即一种字符比另一种多的情况),并且这种重置使我们能够关注从当前点开始的新的波动。同时更新 `diff_with_b[i][j]` 为 `diff[i][j]` 保证了我们记录的是包含至少一次波动的次数差的最大值,从而帮助我们找到可能的最大波动值。
🦆
为什么在更新diff_with_b数组时,即使diff[i][ch]被重置为0,我们仍然需要保留diff_with_b[i][ch]的值不变?
在算法中,`diff_with_b[i][ch]` 记录的是从字符串开始到当前位置,包含至少一次波动的最大次数差。即使 `diff[i][ch]` 被重置为0,我们需要保留 `diff_with_b[i][ch]` 的值不变,因为该值代表了之前的最大波动,可能是整个字符串中的最大值。重置 `diff[i][ch]` 是为了重新开始计算新的波动,但这不影响之前已经达到的最大波动值。
🦆
代码中使用了两层循环来处理26个字母的所有可能对,这种方法在最坏情况下的效率如何?是否存在优化的可能性,尤其是在字符串长度远大于26时?
该代码中的两层循环分别遍历字符串中的每个字符和26个可能的字母,导致算法的时间复杂度为O(n * 26),其中n是字符串的长度。在最坏情况下,这种方法是有效的,因为每个字符都需要与其他25个字符进行比较来更新差异。尽管如此,考虑到实际字符的使用频率,可以对算法进行优化,例如只更新实际在字符串中出现的字符对,而不是固定的26个字母,这可能会减少不必要的计算并提高效率。

相关问题