来源:力扣(LeetCode)
描述:
给你一个长度为 n
、下标从 1 开始的二进制字符串,所有位最开始都是 0
。我们会按步翻转该二进制字符串的所有位(即,将 0
变为 1
)。
给你一个下标从 1 开始的整数数组 flips
,其中 flips[i]
表示对应下标 i
的位将会在第 i
步翻转。
二进制字符串 前缀一致 需满足:在第 i
步之后,在 闭 区间 [1, i]
内的所有位都是 1
,而其他位都是 0
。
返回二进制字符串在翻转过程中 前缀一致 的次数。
示例 1:
输入:flips = [3,2,4,1,5]
输出:2
解释:二进制字符串最开始是 "00000" 。
执行第 1 步:字符串变为 "00100" ,不属于前缀一致的情况。
执行第 2 步:字符串变为 "01100" ,不属于前缀一致的情况。
执行第 3 步:字符串变为 "01110" ,不属于前缀一致的情况。
执行第 4 步:字符串变为 "11110" ,属于前缀一致的情况。
执行第 5 步:字符串变为 "11111" ,属于前缀一致的情况。
在翻转过程中,前缀一致的次数为 2 ,所以返回 2 。
示例 2:
输入:flips = [4,1,2,3]
输出:1
解释:二进制字符串最开始是 "0000" 。
执行第 1 步:字符串变为 "0001" ,不属于前缀一致的情况。
执行第 2 步:字符串变为 "1001" ,不属于前缀一致的情况。
执行第 3 步:字符串变为 "1101" ,不属于前缀一致的情况。
执行第 4 步:字符串变为 "1111" ,属于前缀一致的情况。
在翻转过程中,前缀一致的次数为 1 ,所以返回 1 。
提示:
- n == flips.length
- 1 <= n <= 5 * 104
- flips 是范围 [1, n] 中所有整数构成的一个排列
方法:记录翻转位置的最大值
思路与算法
在第 i 次翻转之后,我们希望 [1, i] 内的所有位都是 1,这等价于「前 i 次翻转中下标的最大值等于 i」。
因此,我们对数组 flip 进行遍历,同时记录翻转下标的最大值。当遍历到位置 i 时,如果最大值恰好等于 i,那么答案加 1。
需要注意数组的下标是从 0 开始的,因此在实际的代码编写中,判断的值为 i+1。
代码:
class Solution {
public:int numTimesAllBlue(vector<int>& flips) {int n = flips.size();int ans = 0, right = 0;for (int i = 0; i < n; ++i) {right = max(right, flips[i]);if (right == i + 1) {++ans;}}return ans;}
};
执行用时:48 ms, 在所有 C++ 提交中击败了70.14%的用户
内存消耗:37.4 MB, 在所有 C++ 提交中击败了99.31%的用户
复杂度分析
时间复杂度:O(n),其中 n 是数组 flips 的长度。
空间复杂度:O(1)。
author:LeetCode-Solution