LeetCode 1375. Bulb Switcher III

, , , ,

Question

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

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

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.

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

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

Solution

比赛的时候没有做出来这个题，当时想的过于复杂。

  • 方法一：主要利用一个maxTurnOn来记录目前为止连续亮的灯是多少个，与当前的index + 1比较（index + 1可以表示目前我们开启了几盏灯）。如果两者相同，则表示达到目标状态，结果加1。
  • 方法二：或者更加简单的方式，用一个变量来维护最远能开的灯，如果当前的个数与这个最远的灯重合，结果加1。

Code

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
// time:O(n) space:O(n)
    public int numTimesAllBlue(int[] light) {
        // 查看连续的长度
        int n = light.length;
        boolean[] turn = new boolean[n];
        int maxTurnOn = 0, res = 0;
        for (int i = 0; i < n; i++) {
            turn[light[i] - 1] = true;
            // 看最长的sequence到哪
            while (maxTurnOn < n && turn[maxTurnOn]) 
                maxTurnOn++;
            // 因为前面的++操作，所以代表i以及之前的已经都亮了
            if (maxTurnOn == i + 1) res++;
        }
        return res;
    }

    // time:O(n) space: O(1)
    public int numTimesAllBlue2(int[] light) {
        int n = light.length;
        int right = 0, res = 0;
        for (int i = 0; i < n; i++) {
            right = Math.max(right, light[i]);
            if (right == i + 1) res++;
        }
        return res;
    }

Reference