之前我们谈了很多递归的算法思路,也讲到了数组、链表等数据结构。今天我们来说一说栈相关的操作,并以Leetcode上面第12题为例,实现一个可以实现返回最小值的栈。
12. 带最小值操作的栈
描述
实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。
你实现的栈将支持push,pop和min操作,所有操作要求都在O(1)时间内完成。
样例
如下操作:push(1),pop(),push(2),push(3),min(), push(1),min()返回1,2,1
我们首先回顾一下Java中栈的使用,以及方法。如下所示:
栈是一种先进后出(FILO)的数据结构,其主要实现是依赖于Vector,这是一种现场安全的数组结构。其主要方法为判断栈为空(empty)、查看栈顶元素(peek)、删除栈顶元素(pop)、压入一个元素(push)。
我们回头思考这个题目,如何实现一个查看最小值的栈。其中多了一个方法public int min();当调用这个方法时,返回目前栈中的最小值。那我们肯定需要一个栈保存最小值。所以我们需要使用双栈实现。
首先我们需要定义两个栈,分别为stack和minStack。分别保存当前数据和最小值。
(1)push方法实现
当我们调用push方法,需要存放元素时,我们将元素存入stack,同时判断minStack中是否有元素,如果没有元素,当前压入的元素就是最小值。如果有元素,那么就要比较了。反正要保证minStack中存放的都是当前stack中的最小值。
(2)pop方法
当调用pop方法,说明要删除一个元素,那么stack和minStack不为空时,同时删除一个元素即可。
(3)min方法
调用此方法,需要返回栈中的最小值,那么我们直接返回minStack中的栈顶元素即可。因为minStack的长度和stack的长度相同,每当stack压入一个元素或者删除一个元素的时候,minStack也会压入当前的最小值和删除minStack栈顶元素。
代码如下:
publicclassMinStack{
publicMinStack(){
// do intialization if necessarystack =newStack(); minStack =newStack(); }
/* * @param number: An integer * @return: nothing */publicvoidpush(intnumber){
// write your code herestack.push(number);
if(minStack.empty()){ minStack.push(number); }
else{
intTopNumber = minStack.peek();
if(TopNumber
/** @return: An integer
*/publicintpop(){// write your code hereintk=stack.peek(); stack.pop(); minStack.pop();
returnk; }
/* * @return: An integer */publicintmin(){
// write your code herereturn(int)minStack.peek(); }
privateStack stack;
privateStack minStack;}
思考:如果实现一个最大栈呢?
这个题目在Lintcode上面有。可以试试。
还可以练练 LeetCode 495,实现栈;
后续我们还会讲解栈相关算法题:
370. 将表达式转换为逆波兰表达式(高难度)
424. 逆波兰表达式求值(中等难度)
领取专属 10元无门槛券
私享最新 技术干货