(程序员面试题精选(02))－设计包含min函数的栈

2022-06-14 IT知识程序员面试题精选

智者不为愚者谋，勇者不为怯者死。这篇文章主要讲述(程序员面试题精选(02))－设计包含min函数的栈相关的知识，希望能为你提供帮助。

设计包含min函数的栈

题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
分析：无论使用链表还是数组实现的栈，push和pop操作的时间复杂度都是O(1)。所以，难点在于实现min使其时间复杂度也是O(1)。高级数据结构的斐波那契堆就是通过一个指向最小元素的指针来实现min函数的，并保证了其时间复杂度为O(1)。因此，该堆栈需要新增一个元素minPoint指针。
假设目前minPoint指针指向最小元素，push(data)，若data比minPoint指向的元素还小，那么minPoint指向data。再 pop()，此时minPoint指向的最小元素不再存在于堆栈中，需要修改minPoint指针。因此，仅仅依靠一个minPoint指针无法顺利实现功能。
考虑用另外一个堆栈minStack来存储minPoint指针依次指向的元素，其中minStack的首元素指向当前的最小元素。当 push(data)，且data比最小元素还小时，把新节点入minStack；否则，直接把data入栈。当pop()时，如果当前要弹出的元素是栈的最小元素，则在minStack中同时出栈，以更改最小元素；否则只弹出当前栈定元素。
自己的思路和作者的思路的不同之处在于，在作者的思路中，每次push(data)时，都同时更新minStack；这样做的好处是在pop时无需判断当前栈定元素是否是最小元素，直接对datas和minStack同时指向pop即可。
具体算法如下：
StackSuppliedMin
stack< type> datas;
stack< int> minStack; //保存最小元素的索引

push(data)
datas.push(data)
if(minStack==NULL || data< datas[minStack.top()])
minStack.push(datas.size()-1)
pop()
if(datas.top() == datas[minStack.top()])
minStack.pop()
datas.pop()
min()
return datas[minStack.top()]
具体代码实现：
// minStatck.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include < iostream>
#include < vector>
#include < cassert>

using namespace std;

template< typename T>
class StackSuppliedMin
public:
vector< T> datas;
vector< size_t> minStack;

void push(T data)
datas.push_back(data);
if (minStack.empty() || data < datas[minStack.back()])
minStack.push_back(datas.size()-1);

void pop()
assert(!datas.empty());
if (datas.back() == datas[minStack.back()])
minStack.pop_back();
datas.pop_back();

T min()
assert(!datas.empty() & & !minStack.empty());
return datas[minStack.back()];

void display()
cout < < "datas = ";
for (unsigned i = 0; i < datas.size(); i ++)
cout < < datas[i] < < " ";
cout < < endl;
cout < < "minStack = ";
for (unsigned i = 0; i < minStack.size(); i ++)
cout < < datas[minStack[i]] < < " ";
cout < < endl;
cout < < "min = " < < datas[minStack.back()] < < endl < < endl;

【(程序员面试题精选(02))－设计包含min函数的栈】;
int _tmain(int argc, _TCHAR* argv[])

StackSuppliedMin< int> s;
s.push(3);
s.display();
s.push(4);
s.display();
s.push(2);
s.display();
s.push(0);
s.display();
s.pop();
s.display();
s.pop();
s.display();
s.push(0);
s.display();

推荐阅读

上一篇：# yyds干货盘点 # 厉害了，Python也能使用动态链接库

下一篇：Cilium Vxlan 跨节点通信过程