数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言程序设计
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的灯泡开关 III
假设我们有一个房间里有 n 个灯泡，从左到右从 1 到 n 编号排列。最初，所有灯泡都是关着的。在时刻 k（对于 0 到 n - 1 范围内的 k），我们打开 light[k] 灯泡。只有当一个灯泡处于开启状态，并且其左边的所有灯泡也都处于开启状态时，这个灯泡才变为蓝色。我们必须找出所有开启灯泡都为蓝色的时刻的数量。这是一个示例 −
输出将是 3，因为时刻为 1、2 和 4。
为了解决这个问题，我们将按照以下步骤操作 −
ret := 0，定义一个集合 x、n := 列表数组的大小、定义一个映射 m
定义基于最大堆的优先队列 pq
对于 0 到 n - 1 范围内的 I
m[light[i]] := i，并将 i 插入到 pq 中
对于 1 到 n 范围内的 I
将 m[i] 插入 x 中
当 pq 不为空，且 pq 的顶部元素在集合 x 中时，
从 pq 中删除
当 (pq 为空或 pq 的顶部>= i) 时，ret:= ret + 1，否则为 0
返回 res
示例 (C++)
让我们看看以下实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int ret = 0;
set <int> x;
int n = light.size();
map <int, int> m;
priority_queue <int, vector <int>, greater <int> > pq;
for(int i = 0; i < n; i++){
m[light[i]] = i;
pq.push(i);
}
for(int i = 1; i <=n; i++){
x.insert(m[i]);
while(!pq.empty() && x.count(pq.top()))pq.pop();
ret += (pq.empty() || (pq.top() >= i));
}
return ret;
}
};
main(){
vector<int> v = {2,1,3,5,4};
Solution ob;
cout << (ob.numTimesAllBlue(v));
}输入
[2,1,3,5,4]
输出
3
更新于: 2020 年 4 月 29 日
370 次浏览
广告