LeetCode 1375. Number of Times Binary String Is Prefix-Aligned【鸽巢原理；树状数组】中等

给你一个长度为 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 * 10^4
flips 是范围 [1, n] 中所有整数构成的一个排列

思考如下：由于 [ 1 , i ] [1,i] [1,i] 内恰好有 i i i 个整数（ i ≥ 1 i \ge 1 i≥1），如果第 i i i 步后「前缀一致」，说明前 i i i 步中的 f l i p s [ 0 , i ) flips[0,\ i) flips[0, i) 恰好组成了 1 1 1 到 i i i 的所有数字。由于每一步只能翻转一个位置，此时必然满足「其他位都是 0 0 0 」的要求。（例如示例 1 的前 4 4 4 个数和前 5 5 5 个数。）

于是问题转换为：如何判断在第 i i i 步是否找到了 [ 1 , i ] [1,i] [1,i] 内的所有整数呢？

解法1 求和

设 s u m sum sum 为和，在第 i i i 步我们加上当前的 f l i p s [ i ] flips[i] flips[i] 。如果 s u m sum sum 等于 i × ( i + 1 ) 2 \dfrac{i \times (i +1)} { 2} 2i×(i+1) ，则说明在第 i i i 步找到了 [ 1 , i ] [1, i] [1,i] 内的所有整数。

class Solution {
public:
    int numTimesAllBlue(vector<int>& flips) {
        int ans = 0;
        long long sum = 0;
        for (int i = 1, n = flips.size(); i <= n; ++i) {
            sum += flips[i - 1];
            if (sum == (long long)i * (i + 1) / 2) ++ans;
        }
        return ans;
    }
};

复杂度分析：

时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)

解法2 求最大值+鸽巢原理

由于题目保证「 flips \textit{flips} flips 是范围 [ 1 , n ] [1,n] [1,n] 中所有整数构成的一个排列」，所以前 i i i 个数互不相同。如果 f l i p s flips flips 前 i i i 个数的最大值等于 i i i ，则说明找到了 [ 1 , i ] [1,i] [1,i] 内的所有整数（如果 [ 1 , i ] [1, i] [1,i] 中有一个数没找到，那最大值必然大于 i i i ，与最大值等于 i i i 矛盾。）

遍历 flips \textit{flips} flips ，维护前 i i i 个数的最大值 mx \textit{mx} mx 。如果 mx = i + 1 \textit{mx} = i+1 mx=i+1 就把答案加一（注意代码中的数组下标需要从 0 0 0 开始，而题目描述是从 1 1 1 开始的）。

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int ans = 0, mx = 0;
        for (int i = 0; i < flips.length; ++i) {
            mx = Math.max(mx, flips[i]);
            if (mx == i + 1) ++ans;
        }
        return ans;
    }
}

复杂度分析：

时间复杂度： O ( n ) O(n) O(n) ，其中 n n n 为 flips \textit{flips} flips 的长度。
空间复杂度： O ( 1 ) O(1) O(1) 。仅用到若干额外变量。

解法3 树状数组/线段树

本题还可用树状数组来求解，虽然时间复杂度较高。因为题目的本质是第 i i i 步后，查询数组区间 [ 1 , i ] [1, i] [1,i] 中 1 1 1 的个数是否等于 i i i ，或者说 [ 1 , i ] [1, i] [1,i] 区间的和是否等于 i i i 。加上单点的翻转操作（单点修改元素从 0 0 0 到 1 1 1 ），很容易想到树状数组来维护动态区间和。

class Solution {
private:
    vector<int> tree;
    int n;
    int lowbit(int i) { return i & -i; }
    void add(int i, int v) {
        while (i <= n) {
            tree[i] += v;
            i += lowbit(i);
        }
    }
    int sum(int i) {
        int ans = 0;
        while (i) {
            ans += tree[i];
            i -= lowbit(i);
        }
        return ans;
    }
public:
    int numTimesAllBlue(vector<int>& flips) {
        n = flips.size();
        tree.resize(n + 1);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            add(flips[i], 1);
            if (sum(i + 1) == i + 1) ++ans;
        }
        return ans;
    }
};

复杂度分析：

时间复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)
空间复杂度： O ( 1 ) O(1) O(1)

memcpy0