智者不为愚者谋,勇者不为怯者死。这篇文章主要讲述(程序员面试题精选(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();
推荐阅读
- Cilium Vxlan 跨节点通信过程
- # yyds干货盘点 # 厉害了,Python也能使用动态链接库
- SVNX使用教程
- Python 函数进阶-递归函数
- 云原生Docker入门 -- 阿里云服务器Linux环境下安装Docker
- html js调试
- [OpenCV实战]28 基于OpenCV的GUI库cvui
- PE工具中的键盘检测工具-KeyBoardTest
- lsd 用于替代ls的rust小工具