方法一：树状数组
<思路：解此题的过程可谓是一波三折。开始的想法很天真，在每次需要PeekMedian的时候，将栈中元素全部拷贝到一个辅助数组，然后对该数组进行排序，很容易找到中间值，时间复杂度为 O（(n^2) lgn），很显然最后超时了。
由于题目说明数据范围为 1~100000，想到了用一个count[]数组来储存每一个数在栈中的个数，然后每一次通过遍历数组累积，当 S[i] = count[1] + count[2] + ... + count[i] >= (n+1)/2 的时候则找到中间值i，时间复杂度为 O（n^2）。
这样显然还会超时，在这个想法的基础上利用树状数组，这种数据结构可以很快的得出前 i 项和，从而可以利用二分查找来找到中间数。于是，push和pop操作时间复杂度为 O（lgn），PeekMedian的复杂度为 O（n (lgn)^2），问题解决。
---------------------
作者：Physicaloser
原文：https://blog.csdn.net/zhayujie5200/article/details/77896067 >
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 1e5 +5;
stack<int> s;
int tree[maxn];
int lowbit(int n)
{
return n & (-n);
}
void update(int x, int y)
{
for(int i = x; i <= maxn; i += lowbit(i))
tree[i] += y;
}
int getsum(int x)
{
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i))
ans += tree[i];
return ans;
}
int Search(int x)
{
int left = 0, right = maxn;
int mid;
while(left <= right)
{
mid = left + (right - left) / 2;
int sum = getsum(mid);
if(sum >= x)
right = mid - 1;
else if(sum < x)
left = mid + 1;
}
return left;
}
int main()
{
int n;
char a[maxn][20];
char po[10], pe[20], pu[10];
strcpy(po,"Pop");
strcpy(pe,"PeekMedian");
strcpy(pu,"Push");
while(cin >> n)
{
for(int i = 0; i < n; i++)
{
cin >> a[i];
if(strcmp(a[i], pe) == 0)
{
if(s.empty() == false)
{
int mid = Search((s.size() + 1) / 2);
cout << mid << endl;
}
else
{
cout << "Invalid" << endl;
}
}
else if(strcmp(a[i], pu) == 0)
{
int key;
cin >> key;
s.push(key);
update(key, 1);
}
else
{
if(s.empty()== false)
{
int key = s.top();
cout << key<< endl;
s.pop();
update(key, -1);
}
else
{
cout << "Invalid" << endl;
}
}
}
}
return 0;
}
方法二：multiset维护两个集合<未做>
链接：https://blog.csdn.net/cstopcoder/article/details/24496853