# leetcode 155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. • push(x) – Push element x onto stack. • pop() – Removes the element on top of the stack. • top() – Get the top element. • getMin() – Retrieve the minimum element in the stack.

The key idea is use a another stack to store the minimum value of the corresponding stack. Put differently, min[i] equals the minimum element where data[i] is the top of this sub-stack.

We can use a full size of min where it’s size equals the data’s, but it’s not necessary.

I have 2 main concerns about the algorithm:

1 We should pop the element in min IFF there’s match of data.top().

2 If we have multiple minima, for example [0, 1, 0] in data, then the min should be [0, 0]. Otherwise, the the pop operation wouldn’t work properly. As a result, we should push the element if x <= min.top().

class MinStack {
public:
void push(int x) {
s.push(x);
if (mins.empty() || x<=mins.top()) {
mins.push(x);
}
}

void pop() {
int temp = s.top();
s.pop();
if (temp == mins.top()) {
mins.pop();
}
}

int top() {
return s.top();
}

int getMin() {
return mins.top();
}

private:
stack<int> s;
stack<int> mins;
};

STL list实现：

class MinStack {
private:
list<int> s;
int min;

public:

MinStack()
{
min=INT_MAX;
}

void push(int x) {
if(x<min) min=x;
s.push_back(x);

}

void pop() {
if(s.back()==min)
{
s.pop_back();
min=INT_MAX;
list<int>::iterator it=s.begin();
while(it!=s.end())
{
if(*it<min) min=*it;
it++;
}
}else
s.pop_back();
}

int top() {
return s.back();
}

int getMin() {
return min;
}
};

python解决方案：

class MinStack:
# @param x, an integer
def __init__(self):
# the stack it self
self.A = []
self.minS=[]
# @return an integer
def push(self, x):
n=len(self.A)
if n==0:
self.minS.append(x)
else:
lastmin=self.minS[-1]
if x<=lastmin:
self.minS.append(x)
self.A.append(x)
# @return nothing
def pop(self):
if len(self.A)>0 and self.A.pop()==self.minS[-1]:
self.minS.pop()
# @return an integer
def top(self):
return self.A[-1]

# @return an integer
def getMin(self):
return self.minS[-1]

python解决方案2：

class MinStack:

def __init__(self):
self.q = []

# @param x, an integer
# @return an integer
def push(self, x):
curMin = self.getMin()
if curMin == None or x < curMin:
curMin = x
self.q.append((x, curMin));

# @return nothing
def pop(self):
self.q.pop()

# @return an integer
def top(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][0]

# @return an integer
def getMin(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][1]

asked Apr 14  in Min Stack  by  charles8135 (180 points)    

0 条评论

• ### leetcode 202 Happy Number

Write an algorithm to determine if a number is "happy".

• ### leetcode 165 Compare Version Numbers

Compare two version numbers version1 and version2. If version1 > version2 ret...

• ### leetcode 205 Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

• ### python 写window服务

import win32serviceutil import win32service import win32event import os impo...

侧滑返回手势是从iOS7开始增加的一个返回操作，经历了两年时间估计iPhone用户大部分都已经忽略了屏幕左上角那个碍眼的back按钮了。之前在网上搜过有关侧滑...

• ### python pyqt5 QMessageBox 消息框

import sys from PyQt5.QtCore import * from PyQt5.QtGui import * from PyQt5.Qt...

• ### Python在计算内存时值得注意的几个问题

我之前的一篇文章，带大家揭晓了 Python 在给内置对象分配内存时的 5 个奇怪而有趣的小秘密。文中使用了sys.getsizeof()来计算内存，但是用这个...

• ### [牛客OI测试赛2]F假的数学游戏(斯特灵公式)

$n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n$

• ### 创建自动滑雪模拟器

关于自治代理，它们的应用和改进，有很多研究。所以在考虑自动驾驶汽车，它可以在没有任何碰撞的情况下在雪地上行驶。不幸的是，没有足够的资源和时间来构建一个真正的机器...