Skip to content

Latest commit

 

History

History
99 lines (78 loc) · 4.55 KB

1057. Stack.md

File metadata and controls

99 lines (78 loc) · 4.55 KB

pat 甲级 1057 Stack

题意概述

堆栈是最基本的数据结构之一，它基于后进先出（LIFO）的原理。基本操作包括Push（将元素插入到顶部位置）和Pop（删除顶部元素）。现在，您应该使用一个额外的操作来实现一个堆栈：PeekMedian——返回堆栈中所有元素的中值。对于 N 个元素，如果 N 为偶数，则将中值定义为第$N/2$个最小元素；如果 N 为奇数，则将中值定义为第$(N+1)/2$个元素。

输入输出格式

输入第一行都包含一个正整数 N。接下来 N 行，每行包含以下 3 种格式之一的命令：

Push key
Pop
PeekMedian

其中 key 是不超过$10^5$的正整数。

对于每个 Push 命令，将键插入堆栈，不输出任何内容。对于每个 Pop 或 PeekMedian 命令，在一行中打印相应的返回值。如果命令无效，则打印无效。

数据规模

$$N<=10^5$$

算法设计

该题有诸多方法可以求解，但求解方法大多不在甲级大纲考核范围之内。换句话说，如果你只是想考甲级的话，可以忽略这个题。

一些比较简单的算法汇总可以参考力扣——数据流的中位数。一些利用高级数据结构的算法汇总可以参考1057. Stack (30)五种解法总结（大杂烩）。这里介绍一种比较简单的一种算法：利用两个multiset查找中位数。

我们可以定义两个multiset的变量s1和s2，分别用来存储栈中数字较小的一半和栈中数字较大的一半，也就是说s1和s2存储的数字应满足：

  1. $max(s1)&lt;=min(s2)$，其中，$max(s1)$表示 s1 中数字的最大值，$min(s2)$表示 s2 中数字的最小值。
  2. $0&lt;=s1.size()-s2.size()&lt;=1$

这样我们可以保证栈中数字的中位数就是 s1 中的最大值（想一想为什么？）。

接下来需要实现针对s1和s2的两个操作：添加元素和删除元素，并且要保证操作结束后s1和s2依然满足前面介绍的两个性质，我们先讨论如何让操作结束后满足性质 1，性质 2 可以通过操作结束后进行的调整操作完成。

  1. 如果要添加一个数$k$，如果要保证s1和s2依然满足性质 1，那么如果$k<max(s1)$，就向 s1 中插入，否则向 s2 中插入。
  2. 如果要删除一个数$k$，那么操作很简单，如果$k$在 s1 中，就从 s1 中删除这个数，否则从 s2 中删除这个数。

操作结束后，由于元素的增删，s1和s2可能会不满足性质 2，这时要进行调整操作。显然，由于每次操作只增删一个元素，不满足性质 2 的情况只有两个情况：$s1.size()-s2.size()==2$或$s2.size()-s1.size()==1$。针对这两种情况进行调整即可，调整的具体步骤是：

  1. 如果$s1.size()-s2.size()==2$，说明 s1 多了一个元素，将$max(s1)$从 s1 中删除并插入到 s2 中即可；
  2. 如果$s2.size()-s1.size()==1$，说明 s2 多了一个元素，将$min(s2)$从 s2 中删除并插入到 s1 中即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
stack<gg> st;
multiset<gg> s1, s2;
void adjust() {
    if (s1.size() - s2.size() == 2) {
        s2.insert(*s1.rbegin());
        s1.erase(prev(s1.end()));
    } else if (s2.size() > s1.size()) {
        s1.insert(*s2.begin());
        s2.erase(s2.begin());
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ki;
    string ci;
    cin >> ni;
    while (ni--) {
        cin >> ci;
        if (ci == "Push") {
            cin >> ki;
            st.push(ki);
            if (s2.empty() or ki < *s1.rbegin()) {
                s1.insert(ki);
            } else {
                s2.insert(ki);
            }
            adjust();
        } else if (ci == "Pop" and not st.empty()) {
            cout << st.top() << "\n";
            if (s1.count(st.top())) {
                s1.erase(s1.find(st.top()));
            } else {
                s2.erase(s2.find(st.top()));
            }
            adjust();
            st.pop();
        } else if (ci == "PeekMedian" and not st.empty()) {
            cout << (*s1.rbegin()) << "\n";
        } else {
            cout << "Invalid\n";
        }
    }
    return 0;
}