import java.util.Scanner;
import java.util.Stack;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Stack<Integer> stack = new Stack<Integer>();
		int[] count = new int[100001];
        int n = in.nextInt();
		for (int i = 0; i < n; i++) {
			String command = in.next();
			if (command.charAt(1)=='u') {
				int num = in.nextInt();
				stack.add(num);
				count[num]++;
			} else if (command.charAt(1)=='o') {
				if (stack.isEmpty())
					System.out.println("Invalid");
				else {
					int m = stack.pop();
					count[m]--;
					System.out.println(m);
				}
			} else {
				if (stack.isEmpty())
					System.out.println("Invalid");
				else
					System.out.println(getMid(count,(stack.size()+1)/2));
			}
		}
	}
	public static int getMid(int[] count, int mid) {
		int sum = 0;
		for (int i = 0; i < count.length; i++) {
			sum += count[i];
			if (sum >= mid)
				return i;
		}
		return 0;
	}
}

import java.util.Scanner;
import java.util.Stack;
import java.util.TreeSet;
public class Main {
	private static TreeSet<Int> s1 = new TreeSet<Int>();
	private static TreeSet<Int> s2 = new TreeSet<Int>();
	private static Stack<Integer> stack = new Stack<Integer>();
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		for(int i = 0;i<n;i++){
			String command = in.next();
			if(command.charAt(1)=='o'){
				if(stack.isEmpty())
					System.out.println("Invalid");
				else{
					int val = stack.pop();
					remove(new Int(val,true));
					System.out.println(val);
				}
			}else if(command.charAt(1)=='e'){
				if(stack.isEmpty())
					System.out.println("Invalid");
				else
					System.out.println(PeekMedian());
			}else{
				int val = in.nextInt();
				stack.add(val);
				add(new Int(val));
			}
		}
	}
	public static void add(Int x) {
	    if (s1.size() == s2.size()) {
	        s2.add(x);
	        s1.add(s2.pollFirst());
	    }
	    else {
	        s1.add(x);
	        s2.add(s1.pollLast());
	    }
	    
	}
	private static void remove(Int val){
		boolean InS2 = s2.contains(val);
		if(s1.size()==s2.size()){
			if(InS2){
				s2.remove(val);
			}else{
				s1.remove(val);
	            s1.add(s2.pollFirst());
			}
		}else if (!InS2) {
	        s1.remove(val);
	    }else{
	    	s2.remove(val);
	        s2.add(s1.pollLast());
	    }
	}
	private static int PeekMedian() {
		return s1.last().val;
	}
	
	private static class Int implements Comparable<Int>{
		int val;
		boolean isRemove = false;
		public Int(int val) {
			this.val = val;
		}
		public Int(int val, boolean isRemove) {
			this.val = val;
			this.isRemove = isRemove;
		}
		@Override
		public int compareTo(Int o) {
			if(this.val>o.val)
				return 1;
			else if(this.val==o.val){
				if(this.isRemove)
					return 0;
			}
			return -1;
		}
	}
}

/*单点更新，区间查询*/
#include <bits/stdc++.h>
using namespace std;
const int AX = 1e5 + 66 ;
int c[AX] ; 
int lowbit( int x ){
	return x & (-x) ; 
}
void update( int x , int v ){
	while( x <= AX ){
		c[x] += v ; 
		x += lowbit(x);
	}
}
int querry( int x ){
	int ans = 0 ;
	while( x ){
		ans += c[x] ;
		x -= lowbit(x) ; 
	}
	return ans ; 
}

int main() {
	int n ;
	char op[20] ;
	scanf("%d",&n) ;
	stack<int>s ;
	int x ;
	for( int i = 0 ; i < n ; i++ ) {
		scanf("%s",op);
		if( op[1] == 'u' ) { //push
			scanf("%d",&x);
			s.push(x);
			update( x , 1 ) ;
		}
		int len = s.size() ;
		if( !len ) {
			printf("Invalid\n");
			continue ;
		}
		if( op[1] == 'o' ) { //pop
			printf("%d\n",s.top());
			update( s.top() , -1 );
			s.pop();
		}
		if( op[1] == 'e' ) { //peekMedian
			int l = 0 , r = AX ;
			int id = ( s.size() + 1 ) >> 1 ; 
			while( l <= r ){
				int mid = ( l + r ) >> 1 ; 
				if( querry(mid) >= id ) r = mid - 1 ;
				else l = mid + 1 ;
			}
			printf("%d\n",l) ;
		}
	}
	return 0 ;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100010,sqr=316;
stack<int> S;
int block[sqr];
int table[MAXN];

void Push() 
{     int x;     cin>>x;     table[x]++;     block[x/sqr]++;     S.push(x);
}

void Pop()
{     int x;     if(S.empty())         cout<<"Invalid"<<endl;     else{         x = S.top();         table[x]--;         block[x/sqr]--;         S.pop();         cout<<x<<endl;     }
}

void PeekMedian()
{     if(S.empty())         cout<<"Invalid"<<endl;     else{         int sum=0,index=0;         int len = S.size();         int mid = (len&1)?(len+1)/2:len/2;         while(sum+block[index] < mid)             sum += block[index++];         int num = index*sqr;         while(sum+table[num] < mid)             sum += table[num++];         cout<<num<<endl;     }
}

int main()
{     int n;     cin>>n;     while(n--)     {         string s;         cin>>s;         if(s[1]=='o')             Pop();         else if(s[1]=='u')             Push();         else if(s[1]=='e')             PeekMedian();     }     return 0;
}

	

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

constexpr int MAXN = 20;
char s[MAXN];
unordered_map<int, int> vis;

struct Compare {
    bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs)
    {
        if (lhs.first == rhs.first) {
            return (lhs.second < rhs.second);
        }
        return (lhs.first < rhs.first);
    }
};

tree <pair<int, int> ,null_type, Compare, rb_tree_tag,
        tree_order_statistics_node_update> Rbtree;
vector <pair<int, int> > A;

int main() {
    
    int N;
    scanf("%d", &N);
    int len = 0;
    pair<int, int> temp;

    while (N--) {
        scanf("%s", s);
        if (strcmp(s, "Pop") == 0) {
            if (len == 0) {
                printf("Invalid\n");
            } else {
                temp = A.at(len - 1);
                printf("%d\n", temp.first);
                A.pop_back();
                --len;
                Rbtree.erase(temp);
            }
        } else if (strcmp(s, "PeekMedian") == 0) {
            if (len == 0) {
                printf("Invalid\n");
                continue;
            }
            if (len % 2 == 0) {
                printf("%d\n", Rbtree.find_by_order(len / 2 - 1)->first);
            } else {
                printf("%d\n", Rbtree.find_by_order((len - 1) / 2)->first);
            }
        } else {
            scanf("%d", &temp.first);
            temp.second = vis[temp.first];
            ++vis[temp.first];
            ++len;
            A.push_back(temp);
            Rbtree.insert(temp);
        }
    }
    return 0;
}

总览

借鉴对顶堆的方法，map红黑树加指针移动，数据范围可以到10^9，时间复杂度平均，空间最差。允许更大的数据范围（10^9），同时保证与题目相同的时间空间复杂度。

思路和复杂度分析

思路很简单，记录当前中值nowp，和大于以及小于中值的数的个数，L和R。
然后下次进行操作时，如果操作数小于当前中值，对L进行操作（push 则加L，pop则减L），大于时同理。操作后，检查L和R，如果不满足nowp为中值，则变更nowp，如果L多了，则将nowp左移（map的树上中找nowp的前驱），左移时间复杂度为直到L满足条件，因为L最多变1，因此找到一个不为0的树上点就可以了，如果使用erase操作，可以保证只左移一次就可以找到新的中值nowp；R的操作同理。
总时间复杂度为。空间复杂度为map中同时存在的不同键值的数目，也就是。这个方法对map的键值范围没有要求，因此数据范围可以到10^9甚至longlong。

算法对比

与线段树时间复杂度相同，都比树状数组二分的好。
在给定值范围内，空间是逐渐增长的，而不是一开始就开满空间，因此空间比树状数组和线段树都好常数级。
特别，如果值扩展到10^9，本方法是在线算法，不需要存储之前的指令；而其他两种都需要使用离线算法，先存储所有指令对值做离散化。

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
map msave;
int K;
int T,L,R,M;
int nowp;
int main()
{
    int K;
    cin>>K;
    char testc[128];
    stack qs;
    T=0;
    L=R=M=0;
    nowp=-1;
    int pn;
    for(int i=0;i<K;++i)
    {
        scanf("%s",testc);
        if(testc[1]=='o')
        {
            if(!qs.empty())
            {
                pn=qs.top();
                qs.pop();
                --msave[pn];
                --T;
                if(pn<nowp) --L;
                else if(pn>nowp) --R;
                printf("%d\n",pn);
            }
            else printf("Invalid\n");
        }
        else if(testc[1]=='e')
        {
            if(T==0) printf("Invalid\n");
            else printf("%d\n",nowp);
        }
        else
        {
            scanf(" %d",&pn);
            qs.push(pn);
            if(msave.find(pn)!=msave.end()) ++msave[pn];
            else msave[pn]=1;
            ++T;
            if(T==1) nowp=pn;
            else if(pn<nowp) ++L;
            else if(pn>nowp) ++R;
        }
        if(T>0)
        {
            auto it=msave.find(nowp);
            for(;L>=((T+1)/2);)
            {
                R+=it->second;
                --it;
                L-=it->second;
            }
            for(;R>(T/2);)
            {
                L+=it->second;
                ++it;
                R-=it->second;
            }
            nowp=it->first;
        }
    }
    return 0;
}

更多PAT甲级题解--acking-you.gtihub.io

最易理解的Stack实现方式，没有树状数组，没有堆！

题目

OJ平台

题目分析

• 关键就是要我们实现以下这个操作：

  PeekMedian -- return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.
  作用是返回栈中第 N/2 小的元素。

• 我们可能很快就会想到排序，然后用STL中的栈来实现，一旦需要排序的时候(PeekMedian操作)就直接sort，然后提交后你会发现----它超时了！😂

好吧，我不偷懒了，自己想想怎么实现这一一个栈，我是用的最朴素的方式实现，通过在栈中多加一个数组实现对元素的排序(这个过程由于是每次入栈和出栈进行排序，所以完全可以用二分找到位置进行插入和删除某个元素)，后面看到很多大佬，不是用堆就是用树状数组，太强了，我还达不到这样的高度啊🤦‍♂️

• 以下是我实现的效率(根大佬们的树状数组还是没得比🤣

代码详解

栈的数据结构实现

这里使用的二分是STL自带的，当然你也可以自己写个二分，这样的话，代码长度会变长🤦‍♂️

//@实现一个栈，用两个数组实现。
struct Stack {
    int *nums;                 //用作栈空间
    int *sort_nums;            //将栈元素排序后的情况
    int length;                //栈的长度
    int capcity;               //栈的最大容量

    Stack(int cap) : nums(nullptr), length(0), capcity(cap), sort_nums(nullptr) {
        nums = new int[capcity];
        sort_nums = new int[capcity];
    }

//@关键在于push和pop操作的处理
    void push(int val) {
        if (!isEmpty()) {
            int pos = upper_bound(sort_nums, sort_nums + length, val) - sort_nums;
            for (int i = length; i > pos; i--) {
                sort_nums[i] = sort_nums[i - 1];
            }
            sort_nums[pos] = val;
        } else {
            sort_nums[length] = val;
        }
        nums[length] = val;
        length++;;
    }

    void pop() {
        if (!isEmpty()) {
            int pos = upper_bound(sort_nums, sort_nums + length, nums[length - 1]) - sort_nums;
            for (int i = pos - 1; i < length; i++) {
                sort_nums[i] = sort_nums[i + 1];
            }
        } else {
            cout << "Invalid" << endl;
            return;
        }
        length--;
        cout << nums[length] << endl;
        return;
    }

    void peekMed() {
        if (isEmpty()) {
            cout << "Invalid" << endl;
        } else {
            cout << sort_nums[(length - 1) / 2] << endl;
        }
    }

    bool isEmpty() {
        return length == 0;
    }
} St(100002);

输入数据和问题解决处理

void solve(const string &s) {//根据字符串的第二个字符进行分类操作
    if (s[1] == 'u') {
        int v;
        cin >> v;
        St.push(v);
    } else if (s[1] == 'o') {
        St.pop();
    } else {
        St.peekMed();
    }
}

void Input() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    int n = N;
    string s;
    while (n--) {
        cin >> s;
        solve(s);
    }
}

整合代码进行提交

应该是最易理解的实现方式了吧！

#include <bits/stdc++.h>

using namespace std;
int N;                         //输入的操作数
//@实现一个栈，用两个数组实现。
struct Stack {
    int *nums;                 //用作栈空间
    int *sort_nums;            //将栈元素排序后的情况
    int length;                //栈的长度
    int capcity;               //栈的最大容量

    Stack(int cap) : nums(nullptr), length(0), capcity(cap), sort_nums(nullptr) {
        nums = new int[capcity];
        sort_nums = new int[capcity];
    }

//@关键在于push和pop操作的处理
    void push(int val) {
        if (!isEmpty()) {
            int pos = upper_bound(sort_nums, sort_nums + length, val) - sort_nums;
            for (int i = length; i > pos; i--) {
                sort_nums[i] = sort_nums[i - 1];
            }
            sort_nums[pos] = val;
        } else {
            sort_nums[length] = val;
        }
        nums[length] = val;
        length++;;
    }

    void pop() {
        if (!isEmpty()) {
            int pos = upper_bound(sort_nums, sort_nums + length, nums[length - 1]) - sort_nums;
            for (int i = pos - 1; i < length; i++) {
                sort_nums[i] = sort_nums[i + 1];
            }
        } else {
            cout << "Invalid" << endl;
            return;
        }
        length--;
        cout << nums[length] << endl;
        return;
    }

    void peekMed() {
        if (isEmpty()) {
            cout << "Invalid" << endl;
        } else {
            cout << sort_nums[(length - 1) / 2] << endl;
        }
    }

    bool isEmpty() {
        return length == 0;
    }
} St(100002);


void solve(const string &s) {//根据字符串的第二个字符进行分类操作
    if (s[1] == 'u') {
        int v;
        cin >> v;
        St.push(v);
    } else if (s[1] == 'o') {
        St.pop();
    } else {
        St.peekMed();
    }
}

void Input() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    int n = N;
    string s;
    while (n--) {
        cin >> s;
        solve(s);
    }
}

int main() {
    Input();
    return 0;
}

#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<stack>
using namespace std;
stack<int>myStack;
int a[100001];
int lowbit(int x) {
	return x & (-x);
}
void add(int val, int index) {
	while (index < 100001) {
		a[index] += val;
		index += lowbit(index);
	}
}
int getSum(int index) {//求下标为1到index的元素的和
	int sum = 0;
	while (index > 0) {//不能为0
		sum += a[index];
		index -= lowbit(index);
	}
	return sum;
}
int PeekMedian(int num) {
	num = (num + 1) / 2;
	int left = 1, right = 100001;
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		int tmp = getSum(mid);//这里tmp是前mid项的和，不能用tmp==num来作为出口，因为 若前面只有a[3]=1，其余均为0，则前100和1000的结果都为1。
		if (tmp < num) {      //其出口应该是left<right
			left = mid+1;
		}
		else {
			right = mid-1;
		}
	}
	return left;
}
int main() {
	//freopen("C:\\Users\\47\\Desktop\\1.txt","r",stdin);
	fill(a, a + 100001, 0);
	int n, x;
	string s;
	cin >> n;
	while (n--) {
		cin >> s;
		if (s == "Push") {
			cin >> x;
			myStack.push(x);
			add(1, x);
		}
		if (s == "Pop") {
			if (myStack.empty())printf("Invalid\n");
			else {
				printf("%d\n", myStack.top());
				add(-1, myStack.top());
				myStack.pop();
			}
		}
		if (s == "PeekMedian") {
			if (myStack.empty())printf("Invalid\n");
			else {
				printf("%d\n", PeekMedian(myStack.size()));
			}
		}
	}
}

#include<bits/stdc++.h>
using namespace std;
int vis[100001];
int main()
{     ios::sync_with_stdio(false);//关闭同步流
    cin.tie(nullptr);     memset(vis,0,sizeof(vis));             stack<int> s;         set<int> od;     int n;cin>>n;         for(int i=0;i<n;i++)     {         string t;cin>>t;             if(t=="Pop")         {             if(s.empty())                 cout<<"Invalid"<<endl;             else              {                     int tmp=s.top();                             if(vis[tmp]>1)                     vis[tmp]--;                 else                  {                     od.erase(od.find(tmp));                                     vis[tmp]--;                 }                                     cout<<tmp<<endl,s.pop();             }         }         if(t=="PeekMedian")         {             if(s.empty())                 cout<<"Invalid"<<endl;             else              {                 vector<int> tmp;//将出现的元素统统放入数组中                 for(auto it=od.begin();it!=od.end();it++)                 {                     for(int i=0;i<vis[*it];i++)                         tmp.push_back(*it);                                     }                 if(tmp.size()%2==0)                 {                     cout<<min(tmp[tmp.size()/2],tmp[tmp.size()/2-1])<<endl;                 }                 else                 {                     cout<<tmp[(tmp.size()+1)/2-1]<<endl;                 }             }         }         if(t=="Push")         {             int x;cin>>x;                         s.push(x);                         if(vis[x]==0)                 od.insert(x);             vis[x]++;         }     }     return 0;
}

#include <iostream>
#include<stack>
#include<string>
using namespace std;
#define lowbit(i) (i&-i)
#define maxn 100010

int c[maxn] = { 0 }, n, tem;
stack<int>s;
string st;
int getsum(int x) {     int res = 0;     for (int i = x; i >= 1; i -= lowbit(i))          res += c[i];     return res;
}

void add(int x, int v) {     for (int i = x; i < maxn; i += lowbit(i))         c[i] += v;
}

void peekmedian() {     int lef = 1, r = maxn, aim = (s.size()+1) / 2,mid;     while (lef < r) {         mid = (lef + r) / 2;         if (getsum(mid)>= aim) {             r = mid;         }         else lef = mid+1;     }     cout << lef << endl;
}


int main() {     cin >> n;     for (int i = 0; i < n; i++) {         cin >> st;         switch (st[1])         {         case'u':cin >> tem;             s.push(tem);             add(tem, 1);             break;         case'o':if (s.empty())cout << "Invalid\n" ;                 else {                     add(s.top(), -1);                     cout << s.top() << endl;                     s.pop();                 }                 break;         case'e':if (s.empty())cout << "Invalid\n";                 else {                     peekmedian();                 }         }              }     return 0;
}

def getMid(cnt,mid):
    suma = 0
    for i in range(0,len(cnt)):
        suma += count[i]
        if suma>= mid:
            return i
    return 0

n = input()
n = int(n)
stack = []
count = [0 for i in range(0,100000)]
for i in range(0,n):
    line = input()
    if line == 'Pop':
        if len(stack)>0:
            m = stack.pop()
            count[m]-=1
            print(m)
        else:
            print("Invalid")
    elif line == 'PeekMedian':
        if len(stack)>0:
            print(getMid(count,((len(stack)+1)//2)))
        else:
            print("Invalid")
    else:
        lst = list(map(str,line.split()))
        m = int(lst[1])
        stack.append(m)
        count[m]+=1

思路： 折半查找法 & 折半插入排序；
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <deque>
#include <fstream>
using namespace std;

#ifndef debug
ifstream ifile("case.txt");
#define cin ifile
#endif

int BinaryFind(deque<int> & a,int& x)
{
    int low = 0;
    int high = a.size() - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (a[mid] > x)
        {
            high = mid - 1;
        }
        else if (a[mid] < x)
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    x = low;
    return -1;
}

void BinaryErase(deque<int> & a, int x)
{
    int tmp = BinaryFind(a, x);
    if (tmp != -1)
    {
        a.erase(a.begin() + tmp);
    }
}

void BinaryInsert(deque<int> & a, int x)
{
    int tmp = x;
    int rlt = BinaryFind(a, tmp);
    if (rlt == -1) {
        a.insert(a.begin() + tmp, x);
    }
    else
        a.insert(a.begin() + rlt, x);
}



int main()
{
    int N;
    string str;
    int tmp;
    int index = 0;
    while (cin >> N) {
        stack<int> s;
        deque<int> media;
        for (int i = 0; i < N; i++)
        {
            cin >> str;
            switch (str[1]) {
            case 'o':// pop
                if (!s.empty()) {
                    tmp = s.top();
                    cout << tmp << endl;
                    s.pop();
                    BinaryErase(media, tmp);
                }
                else {
                    cout << "Invalid" << endl;
                }
                break;
            case 'u':// push
                cin >> tmp;
                s.push(tmp);
                BinaryInsert(media, tmp);
                break;
            case 'e':
                if (!media.empty())
                    cout << media[(media.size() - 1) / 2] << endl;
                else
                    cout << "Invalid" << endl;
                break;
            }
        }
    }
    system("pause");
}

//用vector模拟栈，求PeekMedian即中位数，用map(某个数和对应出现的次数的映射)维护即可。
//可以避免树状数组和线段树的写法。 #include <bits/stdc++.h>
using namespace std;
int n;char str[25];
vector<int> vec;
map<int,int> mp;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%s",str+1);
        if(str[2]=='o'){
            if(vec.empty()) printf("Invalid\n");
            else --mp[vec.back()],printf("%d\n",vec.back()),vec.pop_back();
            continue;
        }if(str[2]=='e'){
            if(vec.empty()) printf("Invalid\n");
            else{
                int sz=vec.size();
                if(sz%2==0){
                    int cnt=0;sz/=2;
                    for(auto &ch:mp){
                        if((cnt+=ch.second)>=sz){
                            printf("%d\n",ch.first);break;
                        }
                    }
                }else{
                    int cnt=0;sz=(sz+1)/2;
                    for(auto &ch:mp){
                        if((cnt+=ch.second)>=sz){
                            printf("%d\n",ch.first);break;
                        }
                    }
                }
            }
            continue;
        }if(str[2]=='u'){
            int x;scanf("%d",&x);
            vec.push_back(x);++mp[x];
            continue;
        }
    }    
    return 0;
} 

#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
const int sqrN = 316;
stack<int> s;
int block[sqrN];
int table[maxn];

void Pop(){
	int elem;
	if(s.empty())
		cout << "Invalid" << endl;
	else{
		elem = s.top();
		table[elem] --;
		block[elem/sqrN] --;
		s.pop();
		cout << elem << endl;
	}
}

void Push(){
	int elem;
	cin >> elem;
	table[elem] ++;
	block[elem/sqrN] ++;
	s.push(elem);
}

void PeekMedian(){
	if(s.empty())
		cout << "Invalid" << endl;
	else{
		int sum_ = 0;
		int idx = 0;
		int len = s.size();
		int mid = (len % 2 == 0) ? (len / 2) : ((len + 1) / 2);
		while(sum_ + block[idx] < mid)
			sum_ += block[idx++];
		int num = idx * sqrN;
		while(sum_ + table[num] < mid)
			sum_ += table[num++];
		printf("%d\n", num);
	}
}

int main(){
	int n;
	cin >> n;
	char op[15];
	while(n--){
		scanf("%s", op);
		if(op[1] == 'o')
			Pop();
		else if(op[1] == 'u')
			Push();
		else if(op[1] == 'e')
			PeekMedian();
	}
	return 0;
}