leetcode 1375

There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.

At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.

Return the number of moments in which all turned on bulbs are blue.

Example 1:

img

1
2
3
Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

Example 2:

1
2
3
Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).

Example 3:

1
2
3
4
Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.

Example 4:

1
2
Input: light = [2,1,4,3,6,5]
Output: 3

Example 5:

1
2
Input: light = [1,2,3,4,5,6]
Output: 6

Constraints:

  • n == light.length
  • 1 <= n <= 5 * 10^4
  • light is a permutation of [1, 2, ..., n]

分析

思路1：每一次电灯记录所有灯中已经被点亮过的最右边的一盏灯的位置 right，再判断从第一盏灯开始到这盏灯为止，一共有多少盏灯被点亮。如果点亮的灯数等于 right 则表示在这个时刻所有已经被点亮的灯都已经变成了绿色。每次判断可以使用树状数组进行查询。算法总体时间复杂度为O(nlogn)，空间复杂度O(n).

思路2: 每一次电灯依然需要记录已经被点亮过的最右边的一盏灯的位置right，然后每一个点灯的时刻判断该点灯的时刻是第几个时刻 i+1。由于light中没有重复的元素，因此如果i+1 == right，则在该时刻从1到right的所有的灯都一定被点亮，即所有被点亮的灯都已经变成了绿色。若 i+1 < right则说明，从1到right的灯中至少存在一个没有被点亮的灯。i+1 > right的情况不存在。算法总体时间复杂度为O(n)，空间复杂度O(1).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 树状数组
class Solution {
public:
    inline int lowbit(int x) {
        return x&(-x);
    }
    
    int getSum(vector<int> &c, int index) {
        int i = index;
        int ret = 0;
        while (i >= 1) {
            ret += c[i];
            i -= lowbit(i);
        }
        return ret;
    }

    void addVal(vector<int> &c, int index, int val) {
        int n = c.size()-1;
        int i = index;
        while (i <= n) {
            c[i] += val;
            i += lowbit(i);
        }
    }

    int numTimesAllBlue(vector<int>& light) {
        int n = light.size();
        vector<int> c(n+1, 0);
        int right = 0;
        int ans = 0;
        for (int i = 0; i < light.size(); ++i) {
            addVal(c, light[i], 1);
            right = max(light[i], right);
            if (right == getSum(c, right))
                ans++;
        }
        return ans;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int n = light.size();
        int right = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            right = max(light[i], right);
            if (i+1 == right)
                ans++;
        }
        return ans;
    }
};