題目:
給你一串陣列
數字都不一樣
叫你找一組三個數字
左邊中間右邊
分別大於大約 或是 小於小於
問你有幾組這樣的數字
思路:
我想了兩個方法
一個成功 一個失敗
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;
}
};
```