题目概述:

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。

示例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
class MinStack(object): def __init__(self): """ initialize your data structure
here. """ self.stack = [] # 存放所有元素 self.minStack = [] #
存放每一次压入数据时,栈中的最小值(如果压入数据的值大于栈中的最小值就不需要重复压入最小值,小于或者等于栈中最小值则需要压入) def push(self,
x): """ :type x: int :rtype: void """ self.stack.append(x) if not self.minStack
or self.minStack[-1]>=x: self.minStack.append(x) def pop(self): #
移除栈顶元素时,判断是否移除栈中最小值 """ :rtype: void """ if self.minStack[-1]==self.stack[-1]:
del self.minStack[-1] self.stack.pop() def top(self): """ :rtype: int """
return self.stack[-1] def getMin(self): """ :rtype: int """ return
self.minStack[-1]
 

以下是Java版本:
1.class MinStack {   2.    // stack: store the stack numbers  
3.    private Stack<Integer> stack = new Stack<Integer>();  
4.    // minStack: store the current min values  
5.    private Stack<Integer> minStack = new Stack<Integer>();   6.  
7.    public void push(int x) {  
8.        // store current min value into minStack  
9.        if (minStack.isEmpty() || x <= minStack.peek())  
10.            minStack.push(x);   11.        stack.push(x);   12.    }   13.  
14.    public void pop() {  
15.        // use equals to compare the value of two object, if equal, pop both of them  
16.        if (stack.peek().equals(minStack.peek()))  
17.            minStack.pop();   18.        stack.pop();   19.    }   20.  
21.    public int top() {   22.        return stack.peek();   23.    }   24.  
25.    public int getMin() {   26.        return minStack.peek();   27.    }  
28.}  
【分析】

这道题的关键之处就在于 minStack 的设计,push() pop() top() 这些操作Java内置的Stack都有,不必多说。

我最初想着再弄两个数组,分别记录每个元素的前一个比它大的和后一个比它小的,想复杂了。

第一次看上面的代码,还觉得它有问题,为啥只在 x<minStack.peek() 时压栈?如果,push(5), push(1), push(3)
这样minStack里不就只有5和1,这样pop()出1后, getMin()
不就得到5而不是3吗?其实这样想是错的,因为要想pop()出1之前,3就已经被pop()出了。. 

minStack 记录的永远是当前所有元素中最小的,无论 minStack.peek() 在stack 中所处的位置。

技术
©2019-2020 Toolsou All rights reserved,
数字滚动抽奖小程序VaR - 风险价值 - 蒙特卡罗法 - Python百度网盘偷偷更新,终于实现免费不限速了! Chrome OS,对程序员和Windows意味着什么?,互联网营销华为Mate 40 Pro+ 5G曝光:徕卡电影镜头、陶瓷机身Qt学习2——.pro文件和.h文件介绍python:将一个文件转换为二进制文件(binary)第十一届蓝桥杯C/C++ 大学 B 组大赛软件类省赛网站手机号码抓取方式蚂蚁集团香港IPO获得中国证监会批准