二进制字符串前缀一致的次数
难度:
标签:
题目描述
代码结果
运行时间: 48 ms, 内存: 21.9 MB
/*
思路:
使用 Java Stream 的话,我们可以利用 IntStream 和累加器来计算前缀一致的次数。
与传统方法类似,我们需要维护当前的最大翻转位置。
*/
import java.util.stream.IntStream;
public class Solution {
public int numTimesAllBlue(int[] flips) {
int[] maxFlip = {0};
return (int) IntStream.range(0, flips.length)
.filter(i -> {
maxFlip[0] = Math.max(maxFlip[0], flips[i]);
return maxFlip[0] == i + 1;
})
.count();
}
}
解释
方法:
本题解的思路是通过维护一个最大翻转位置的变量来判断是否满足前缀一致的条件。遍历flips数组,每次更新最大翻转位置,如果当前最大翻转位置小于等于当前步数(i+1),则说明在当前步骤下,前缀一致的条件得到满足,因此结果计数加1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在判断前缀一致时,我们依赖于最大翻转位置max是否小于等于当前步数i+1?这样的条件是如何确保前缀一致的?
▷🦆
在更新最大翻转位置max时,为什么只检查当前翻转位置flips[i]是否大于max而没有其他条件?是否有可能因为翻转顺序的不同而影响判断结果?
▷🦆
如果数组flips中存在重复的数字,这种情况下算法的行为会如何改变?会对最终的前缀一致次数计算产生什么影响?
▷🦆
算法中使用的变量max初始化为-1而不是0的原因是什么?
▷