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:
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:
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:
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:
Input: light = [2,1,4,3,6,5] Output: 3
Example 5:
Input: light = [1,2,3,4,5,6] Output: 6
Constraints:
n == light.length1 <= n <= 5 * 10^4lightis a permutation of[1, 2, ..., n]
这道题有点意思。给定n个灯泡，如果某个灯泡及其左边的所有灯泡都亮着，则这个灯泡会变成蓝色。刚开始时所有灯泡都是关着的，现在会进行n次开灯的操作，但开灯的顺序不确定。问有多少次开灯操作会使得亮着的所有灯都是蓝色的。
描述起来有点绕，大家看看题目中的示意图就很清楚了。
暴力解法是每开一次灯，都遍历其左边所有灯是否都亮着，时间复杂度是O(n^2)，我估计会TLE，我没试过。
我的O(n)的方法如下。在开灯的过程中，记录当前开过的灯的最大编号max_id，同时记录目前已经亮着的灯的数目n。如果max_id==n，则此次开灯操作能使得亮着的灯都变成蓝色。举个例子，如果max_id==n==5，说明目前亮着5盏灯，且这5盏灯的最大编号是5，那说明其余亮着的灯的编号肯定是1,2,3,4，所以这5盏灯都会变成蓝色。
完整代码如下：
class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int ans = 0;
int curmax = 0;
for (int i = 0; i < light.size(); ++i) {
curmax = max(curmax, light[i]);
if (curmax == i + 1)++ans;
}
return ans;
}
};本代码提交AC，用时112MS。