题目:
给你一串阵列
数字都不一样
叫你找一组三个数字
左边中间右边
分别大于大约 或是 小于小于
问你有几组这样的数字
思路:
我想了两个方法
一个成功 一个失败
1
标准的暴力+dp
每次都往前看有多少数字可以被他拿去当组员
如果那个数字本来就有组员就可以成为新的组
姆咪
```cpp
class Solution {
public:
int numTeams(vector<int>& rating)
{
int res = 0;
int len = rating.size();
vector<int> paper(len,0);
vector<int> paper2(len,0);
for(int i = 0 ; i < len ; i ++)
{
for(int j = 0 ; j < i ; j ++)
{
if(rating[j] < rating[i])
{
paper[i]++;
res += paper[j];
}
if(rating[j] > rating[i])
{
paper2[i]++;
res += paper2[j];
}
}
}
return res;
}
};
```
2
我觉得这个应该是可以改进的
就是我用priority queue
放数字跟他们有多少组员
然后每次有新数字的时候就放进去
然后pop可以变成组员的数字
直到数字不满足大于 或是 小于
然后把pop出来的
放回去两种
一种是原本的
一种是多了一个组员
然后数字变大成当前的
这个做法是对的 但是会超时
因为虽然但是
反正就拿进拿出 又多了好几组
会很麻烦
对ㄚ
```cpp
class Solution {
public:
int numTeams(vector<int>& rating)
{
int res = 0;
int len = rating.size();
priority_queue<pair<int,int>> paper;
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<> > paper
2;
vector<pair<int,int>> save;
for(int i = 0 ; i < len ; i ++)
{
paper.push({rating[i],1});
paper2.push({rating[i],1});
save.clear();
while(!paper.empty() && paper.top().first > rating[i])
{
pair<int,int> k = paper.top();
paper.pop();
save.push_back(k);
k.first = rating[i];
k.second ++;
if(k.second >= 3)res++;
else save.push_back(k);
}
for(auto k : save)
{
paper.push(k);
}
save.clear();
while(!paper2.empty() && paper2.top().first < rating[i])
{
pair<int,int> k = paper2.top();
paper2.pop();
save.push_back(k);
k.first = rating[i];
k.second ++;
if(k.second >= 3)res++;
else save.push_back(k);
}
for(auto k : save)
{
paper2.push(k);
}
}
return res;
}
};
```