思路:
通过增加一个辅助栈保存每个状态对应的最小值。栈实现的不完整,应该还包含empty()等常规函数。
#include <iostream>
#include <stack>
using namespace std; template <typename T> class StackWithMin
{
public:
void push(const T& value);
void pop();
T getMin(); private:
stack<T> DataStack;
stack<T> MinStack;
}; template <typename T> void StackWithMin<T>::push(const T& value)
{
DataStack.push(value); if(MinStack.size() == || value < MinStack.top())
MinStack.push(value);
else
MinStack.push(MinStack.top());
} template <typename T> void StackWithMin<T>::pop()
{
DataStack.pop();
MinStack.pop();
} template <typename T> T StackWithMin<T>::getMin()
{
return MinStack.top();
} int main()
{
StackWithMin<int> s; cout<<"push 5"<<endl;
s.push();
cout<<"Min: "<<s.getMin()<<endl; cout<<"push 3"<<endl;
s.push();
cout<<"Min: "<<s.getMin()<<endl; cout<<"push 1"<<endl;
s.push();
cout<<"Min: "<<s.getMin()<<endl; cout<<"pop"<<endl;
s.pop();
cout<<"Min: "<<s.getMin()<<endl; cout<<"pop"<<endl;
s.pop();
cout<<"Min: "<<s.getMin()<<endl; cout<<"push 10"<<endl;
s.push();
cout<<"Min: "<<s.getMin()<<endl;
}
测试结果:
push
Min:
push
Min:
push
Min:
pop
Min:
pop
Min:
push
Min:
【剑指offer 面试题21】包含min函数的栈的更多相关文章
-
剑指Offer:面试题21——包含min函数的栈(java实现)
问题描述: 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数.在该栈中,调用min,push及pop的时间复杂度都是O(1). 思路:加入一个辅助栈用来存储最小值集合 (这里要注 ...
-
剑指offer面试题30.包含min函数的栈
一开始写的垃圾代码,push和pop都是O(N) class Solution { public: vector<int> vec; int min_val=INT_MAX,min_cnt ...
-
剑指Offer - 九度1522 - 包含min函数的栈
剑指Offer - 九度1522 - 包含min函数的栈2013-12-01 23:44 题目描述: 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数. 输入: 输入可能包含多个测 ...
-
剑指offer(20)包含min函数的栈
题目描述 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数. 题目分析 首先一开始我们分析得到最小值肯定要比较嘛,和栈里面的数据一一比较,但是栈这种数据结构,你又只能和栈顶弹出来的 ...
-
剑指offer二十之包含min函数的栈
一.题目 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数. 二.思路 用一个栈dataStack保存数据,用另外一个栈minStack保存依次入栈最小的数.每次元素存入minSt ...
-
【剑指Offer】20、包含min函数的栈
题目描述: 定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1)). 解题思路: 使用两个stack,一个为数据栈,另一个为辅助栈.数据栈 ...
-
《剑指offer》面试题21 包含min函数的栈 Java版
(min函数的作用是返回栈内最小值) 首先这个栈要具有普通栈所具有的push()和pop()方法,那么内部一定包含一个Stack.至于还要能实现min函数,而且还是在O(1)时间复杂度内,我们不得不考 ...
-
《剑指offer》面试题21—包含min函数的栈
题目:定义栈数据结构,并在该数据结构中实现一个能获得栈最小元素的函数min.要求push,min,pop时间都是O(1). 思路:要用一个辅助栈,每次有新元素压栈时辅助栈压入当前最小元素:min函数直 ...
-
剑指offer-面试题21.包含min函数的栈
题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数. 在该栈中,调用min,push及pop的时间复杂度都是O(1). 这一题实际上需要一个辅助栈存储最小值: 1.在模板类定 ...
-
题目21 包含Min函数的栈
///////////////////////////////////////////////////////////////////////////////////// // 3. 题目21 包含 ...
随机推荐
-
n维数组实现(可变参数表的使用)
首先先介绍一下可变参数表需要用到的宏: 头文件:#include<cstdarg> void va_start( va_list arg_ptr, prev_param ); type v ...
-
MSSQL 2012 拒绝了对对象 &#39;extended_properties&#39; (数据库 &#39;mssqlsystemresource&#39;,架构 &#39;sys&#39;)的 SELECT 权限
查看数据库的表的时候报如下错误: MSSQL 拒绝了对对象 ) 解决方法: 在数据库里相应的用户权限中,把db_denydatareader的复选框的勾去掉.db_denydatareader是拒绝访 ...
-
OpenCV SIFT原理与源码分析
http://blog.csdn.net/xiaowei_cqu/article/details/8069548 SIFT简介 Scale Invariant Feature Transform,尺度 ...
-
css 权威指南笔记( 五)结构和层叠之三种样式来源
CSS中的样式一共有三种来源:创作人员.读者和用户代理,来源的不同会影响到样式的层叠方式 首先,创作人员(author's+style)样式应该是我们最熟悉的,如果你是一个前端开发者,那么你写的那些样 ...
-
Jsp、Servlet
1 forward.redirect forward 转发是服务器行为,浏览器根本不知道服务器发送的内容是从哪儿来,所以它的地址栏中还是原来的地址. redirect 重定向是客户端行为.redire ...
-
js拉起或下载app
产品提了个需求,通过手机网页判断是否安装了自己公司app,如果安装了则拉起app,没有安装则跳转到下载页. 经过各种查阅资料尝试总结了一个还算可以的办法. 拉起app的原理就是js和原生统一好一个地址 ...
-
mysqldumpslow的使用简介
mysqldumpslow的使用:比如我们要查询按时间返回前5条日志信息,格式如下:mysqldumpslow -s t -t 5 /var/log/mysql/slowquery_20170303. ...
-
c/c++ SQLite3的常用使用方法;
下面测试用的sqlite例子;大家可以参考使用; #include "CppSQLite3.h" Class TestSqlite{ //定义db指针 private: CppSQ ...
-
201521123081《java程序设计》 第7周学习总结
1. 本周学习总结 以你喜欢的方式(思维导图或其他)归纳总结集合相关内容. 参考资料:XMind 2. 书面作业 Q1. ArrayList代码分析 1.1 解释ArrayList的 contains ...
-
12.2、多线程通信:queue
queue: 什么是队列:是一种特殊的结构,类似于列表.不过就像排队一样,队列中的元素一旦取出,那么就会从队列中删除. 线程之间的通信可以使用队列queue来进行 线程如何使用queue.Queue[ ...