二进制字符串前缀一致的次数【LC1375】
给你一个长度为 n
、下标从 1 开始的二进制字符串,所有位最开始都是 0
。我们会按步翻转该二进制字符串的所有位(即,将 0
变为 1
)。
给你一个下标从 1 开始的整数数组 flips
,其中 flips[i]
表示对应下标 i
的位将会在第 i
步翻转。
二进制字符串 前缀一致 需满足:在第 i
步之后,在 闭 区间 [1, i]
内的所有位都是 1 ,而其他位都是 0 。
返回二进制字符串在翻转过程中 前缀一致 的次数。
技巧题,二十分钟想出来了
思路
由于每位只翻转一次,不存在0->1->0的情况,因此如果在第 i 步之后,在 闭 区间 [1, i] 内的所有位都是 1时,那么前i步翻转的位一定是[1, i] 内的所有位。因此可以记录截止第i步,翻转位的最大值,如果与i相等,那么代表前缀一致,次数+1
实现
class Solution { public int numTimesAllBlue(int[] flips) { int n = flips.length; int res = 0; int mx = 0; for (int i = 0; i < n; i++){ mx = Math.max(mx, flips[i]); if (mx == i + 1){ res++; } } return res; } }
复杂度
- 时间复杂度:O ( n )
- 空间复杂度:O ( 1 )