L3-002 特殊堆栈

题目链接

L3-002 特殊堆栈

分析

本题难点在于取得元素中值，可以视为取得第 $k$ 小的值（$k$ 为 $N/2$ 或者 $(N-1)/2$）

维护一个额外的数组 $v$，在每次 push 操作时，二分将其插入到数组中第一个大于它的数之前，这样每次需要返回中值时只需要访问 $v[n/2]$ 即可，pop 操作时同样二分后删除

其余操作使用堆栈模拟即可

代码实现

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

stack<int> s;
vector<int> v;

int main()
{
    int n, key;
    cin >> n;
    string in;
    vector<int>::iterator it;
    for (int i = 0; i < n; ++i)
    {

        cin >> in;
        if ((in == "Pop"  in == "PeekMedian") && !v.size())
        {
            cout << "Invalid" << endl;
            continue;
        }
        if (in == "Push")
        {
            cin >> key;
            s.push(key);
            it = lower_bound(v.begin(), v.end(), key);
            v.insert(it, key);
        }
        if (in == "Pop")
        {
            cout << s.top() << endl;
            it = lower_bound(v.begin(), v.end(), s.top());
            v.erase(it);
            s.pop();
        }
        if (in == "PeekMedian")
        {
            int s = v.size();
            cout << v[(s + (s % 2)) / 2 - 1] << endl;
        }
    }
    return 0;
}