题目
今天参加了清华Labmu校园极客社的面试。面试时间不长，主要问了掌握哪些技术以及参与项目的意向。但问了几个有关数据结构的问题还算有趣。和大家分享一下。
- 问题一：如何用两个栈实现一个队列，要求均摊O(1)时间复杂度。
- 问题二：如何实时获得一个栈中元素的最小（大）值。注意不取出，只需知道最值。也就是实现一个随时都能知道栈中最小值的特殊栈。
- 问题三：如何实时获得一个队列中元素的最小（大）值。注意不取出，只需知道最值。也就是实现一个随时都能知道栈中最小值的特殊队列。
分析
问题1
- 假设栈A和栈B，容量分别为m和n（要求m<=n）。
- 入队操作：将元素压入栈A。
- 出队操作：如栈B非空，则弹栈，弹出元素为出队元素；如栈B为空，则将栈A中所有元素弹出并压入栈B，同时将B中栈顶元素弹出。
-
应注意2点：
- 栈A和栈B实现的队列容量为m+1。可以这样考虑，当栈A中有2个元素而栈B为空时，做出队操作。此后，B中有1个元素，A为空。此时入队m个元素。此时无法再入队。所以认为极限情况下保证安全的队列容量为m+1。
- m<=n。如m>n，当栈A满时，无法将所有栈A中元素弹栈并压入栈B。
- 实现
#include <iostream>
#include <stack>
using namespace std;
template <typename type>
class twoStacksQueue {
public:
void push(type item) {
stka.push(item);
}
type pop() {//简化实现, 没有考虑队空的情况
type item;
if (stkb.empty()) {
while (!stka.empty()) {
item = stka.top(); stka.pop();
stkb.push(item);
}
}
item = stkb.top(); stkb.pop();
return item;
}
private:
stack<type> stka, stkb;
};
int main() {
twoStacksQueue<int> que;
int item;
que.push(1); que.push(2);que.push(6);
for (int i = 0; i != 3; ++i) {
cout << que.pop() << " ";
}
return 0;
}
问题2
- 考虑最小值，只需维护一个最小值栈minstack即可。设辅助栈minstk。
-
入栈操作：
当主栈有元素E入栈时，比较minstk栈顶元素A与元素E，如A>=E，则主栈和辅助栈minstk都压入元素E。如A<E，则只在主栈中压入元素E。 -
出栈操作：
当主栈需要出栈时，将主栈栈顶元素E弹出，同时比较minstk栈顶元素A与元素E。如A=E，那么minstk也弹栈；如E>A，则minstk不做任何操作。 - 取最小值操作：栈顶元素就是最小值。
- 如果对辅助栈的深度有要求且相同元素较多的情况，可以采用设置一个最小值计数栈的方法优化。
struct minStkNode {
int count, curmin;//记录当前最小值和出现的次数
minStkNode(int min): count(1), curmin(min) {}
};
class MinStack {
public:
void push(int x) {
stk.push(x);
if (minstk.empty())
minstk.push(minStkNode(x));
else {
auto &minval = minstk.top();
if (minval.curmin > x)
minstk.push(minStkNode(x));
else if (minval.curmin == x)
++minval.count;
}
}
void pop() {
int cur = stk.top(); stk.pop();
auto &minval = minstk.top();//此处使用引用, 直接修改minstk的栈顶元素, 而非创建其副本
if (cur == minval.curmin && --minval.count == 0)
minstk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return minstk.top().curmin;
}
private:
stack<int> stk;
stack<minStkNode> minstk;
};
问题3
这题应该是三道题中最难的一道。这个问题需要一种特殊的数据结构：单调队列。单调队列能够维护一个下界不减的一个数据区间内的最值。
这里先解释一下什么叫做下界不减。假设一个数组arr[10] = {1, 4, 2, 7, 8, 6, 5, 4, 3, 9};
index 0 1 2 3 4 5 6 7 8 9
value 1 4 2 7 8 6 5 4 3 9
这里下界不减表示，在一个动态求某个范围内最小值的过程中，范围的下界不会减小。比如这样一个过程，我需要知道(0,1)->(0, 3)->(2, 4)->(2,7)->(3, 8)->(7, 9)。格式(BOTTOM, TOP)表示从index=BOTTOM到index=TOP范围内的最小值。我们可以发现下界是这样增长的0->0->2->2->3->7。
单调队列的出入队操作：
需要维护一个下标队列和单调递增队列。
-
入队操作：
比较入队元素A与队尾元素B，如A>=B，则将A送入单调队列，同时将元素A的下标送入下标队列；如A<B，则将队尾B出队，同时B的下标也要从下标队列的队尾出队（普通队列不支持队尾出队操作，因此使用vector实现），继续比较A与新的队尾元素，重复步骤直到A>=B时将A入队，同时注意将A的下标送入下标队列。 -
出队操作：
比较所需范围的下界bottom和当前下标队列的队头元素值head，如head<bottom则将下标队列队头元素出队，对应单调队列中的队头也出队，重复上述步骤直到bottom<=head，此时单调队列中的队头元素即为所求范围内的最小值。
根据出队的操作，我们可以发现，下标队列的队头元素出队会导致下标队列的队头元素不断增大（下标队列中的下标值也是递增的），这就是为什么我们要求下界不减的原因。
注意
- 单调队列和下标队列中，单调队列中的元素值和下标队列中对应位置的下标是一一对应的。
- 另外我们应该确认一点，任一一个时刻单调队列的队头元素是当前范围内的最小值。
步骤
只要我们在对队列进行入队出队操作时，同样对这样一个单调递增队列也做相应操作就可以了。假设原队列叫A，单调队列称为B，这题不需要下标队列。
- 入队操作：队A入队，同时队B也入队（不是普通的入队操作，而是单调队列的入队，具体看上面）；
- 出队操作：队A出队，出队元素为item，比较item和队B队头元素head，如item=head，队B也出队，如item>head，队B不做任何操作。
-
取最小值操作：队B的队头元素值就是最小值。
上述三个操作就实现了一个随时可以知道队列中最小值的特殊队列。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
template <typename type>
class minQueue {
public:
void push(const type&);
type front();
void pop();
type extractMin();
bool empty() {
return que.empty();
}
private:
queue<type> que;
vector<type> minque;
};
template <typename type>
void minQueue<type>::push(const type& item) {
que.push(item);
while (!minque.empty() && minque.back() > item) {
minque.pop_back();
}
minque.push_back(item);
}
template <typename type>
type minQueue<type>::front() {
return que.front();
}
template <typename type>
void minQueue<type>::pop() {
type item = que.front(); que.pop();
if (item == minque.front()) {
minque.erase(minque.begin());
}
}
template <typename type>
type minQueue<type>::extractMin() {
return minque.front();
}
int main() {
minQueue<int> minq;
int item;
for (int i = 0; i != 10; ++i) {
cin >> item;
minq.push(item);
}
while (!minq.empty()) {
cout << "current minval: " << minq.extractMin() << endl;
minq.pop();
}
return 0;
}
