题目：用O（1）的时间复杂度求解栈中的最小元素。
栈是一种我们经常使用的数据结构，有压栈、弹栈、取栈顶元素、判断栈是否为空、获取栈中元素个数等方法，我们先来实现它：
实现栈结构有两种方法，一种是用数组，一种是用链表。数组实现很简单，我用链表来实现。
#方法：链表实现
class LNode:
'''模拟链表节点'''
def __init__(self,arg):
self.data=arg
self.next=None
class Stack:
'''模拟栈'''
def __init__(self):
#phead=LNode(None)
self.data=None
self.next=None
#判断栈是否为空,如果为空返回True，否则返回false
def isEmpty(self):
if self.next is None:
return True
else:
return False
#返回栈的大小
def size(self):
size=0
p=self.next
while p is not None:
size+=1
p=p.next
return size
#返回栈顶元素
def top(self):
if not self.isEmpty():
return self.next.data
else:
print("栈为空")
return None
#返回栈底元素
def bottom(self):
if not self.isEmpty():
p=self.next
while p.next is not None:
p=p.next
return p.data
else:
print("栈为空")
return None
#弹栈
def pop(self):
if not self.isEmpty():
self.next=self.next.next
print("弹栈成功")
else:
print("栈已为空")
return None
#压栈
def push(self,item):
tmp=LNode(item)
p=self.next
self.next=tmp
tmp.next=p
print("入栈成功")
#清空栈
def destroy(self):
self.next=None # 我这里为了实现简单，并没有考虑垃圾回收机制
print("栈已清空")
我这里为了实现简单，并没有考虑垃圾回收机制。
实现起来很简单。栈是一种先进先出的数据结构，我们只能访问栈顶元素，所以如果要找栈中的最小元素就要先全部出栈，进入新的栈，同时找出最小值，在将新栈中的元素出栈，还原。
或者也可以用一个变量来记录栈底位置，遍历得最小值。
在算法设计中我们通常用空间换时间的方法，来降低时间复杂度。
这里我们直接改一下原来的栈的实现方式，利用两个栈来存储元素——栈A和栈B，栈A的功能和原来的栈相同，存储所有的数据，栈B用来存储当前栈A的最小元素，且栈顶总是栈A中的最小值。
栈的实现思路为：当需要压栈时，先判断入栈元素是否小于等于栈B的栈顶元素，如果小于等于，则同时入栈A和栈B，否则，只入栈A。当需要弹栈时，先判断栈A的栈顶元素是否小于等于栈B的栈顶元素，如果小于等于，则栈A和栈B同时弹栈，否则只有栈A弹栈。
这很好理解，无论什么时候，栈B的栈顶元素永远是栈A中的最小元素。
---+ +---+ +---
===|__3__|===|__ __|===
===|__9__|===|__ __|===
===|__5__|===|__ __|===
===|__3__|===|__ __|===
===|__7__|===|__ __|===
===|__5__|===|__3__|===
===|__4__|===|__3__|===
===|__8__|===|__4__|===
===|__6__|===|__6__|===
=====max=======min=====
下面来实现这种栈结构：
class MyStack():
def __init__(self):
self.elemStack=Stack()#用来储存栈
self.minStack=Stack()#用来保存栈中的最小值，当前栈的最小值即为栈顶元素
#压栈
def push(self,item):
"""
若当前元素的值比比minStack的栈顶元素小，或者“相等”！！都入栈
这里是重点，网上很多文章，他们用的Java写的，但是同样没注意到这点！
他们都只注意到当前元素要比minStack栈顶元素小，没注意到相等的情况。
如果栈elemStack中为1-2-3-1-2-4，则minStack为：1-2-3-4(栈顶在前)，
如果第一个1出栈，则elemStack:2-3-1-2-4,minStack:2-3-4,显而易见，
最小值为1，但是minStack栈顶为2，
所以出错了！！！！！！
很多教材，和网上文章都没注意到。
"""
#先判断
if self.minStack.isEmpty():
return self.elemStack.push(item), self.minStack.push(item)
if item<=self.minStack.top():
#相等或小于，都入栈
return self.elemStack.push(item),self.minStack.push(item)
else:
#大于,只存储在elemstack
return self.elemStack.push(item)
def pop(self):
"""
如果elemStack的栈顶元素等于minStack的栈顶元素，则两个都弹栈，如果elemStack的栈顶元素大于minStack的栈顶元素，则只有elemStack弹栈
"""
if self.elemStack.top()==self.minStack.top():
return self.elemStack.pop(),self.minStack.pop()
else:
return self.elemStack.pop()
def minitem(self):
#返回最小值
return self.minStack.top()
因为新的栈结构有两个栈，就没用继承，而且我就写了出栈、入栈以及返回最小元素，三个方法。这里用了额外的空间，但是在找最小元素时，只需要调用栈的stack.minitem()方法即可。时间复杂度为O(1)。
主函数：
if __name__ == '__main__':
s=MyStack()
s.push(4)
s.push(5)
s.push(7)
print("此时栈中的最小值为：",s.minitem())
s.push(3)
print("此时栈中的最小值为：",s.minitem())
s.push(5)
s.push(9)
print("此时栈中的最小值为：",s.minitem())
s.push(3)
print("此时栈中的最小值为：",s.minitem())
s.pop()
print("此时栈中的最小值为：",s.minitem())
运行结果：
image.png
还是这些题目简单，LeetCode上的题对现在的我来说有点难度。。。
全部代码：
#栈：压栈、弹栈、取栈顶元素、判断栈是否为空、获取栈中元素个数、清空栈。先进后出
#方法：链表实现
class LNode:
def __init__(self,arg):
self.data=arg
self.next=None
class Stack:
#模拟栈
def __init__(self):
#phead=LNode(None)
self.data=None
self.next=None
#判断栈是否为空,如果为空返回True，否则返回false
def isEmpty(self):
if self.next is None:
return True
else:
return False
#返回栈的大小
def size(self):
size=0
p=self.next
while p is not None:
size+=1
p=p.next
return size
#返回栈顶元素
def top(self):
if not self.isEmpty():
return self.next.data
else:
print("栈为空")
return None
#返回栈底元素
def bottom(self):
if not self.isEmpty():
p=self.next
while p.next is not None:
p=p.next
return p.data
else:
print("栈为空")
return None
#弹栈
def pop(self):
if not self.isEmpty():
self.next=self.next.next
print("弹栈成功")
else:
print("栈已为空")
return None
#压栈
def push(self,item):
tmp=LNode(item)
p=self.next
self.next=tmp
tmp.next=p
print("入栈成功")
#清空栈
def destroy(self):
self.next=None
print("栈已清空")
#打印栈
def showStack(self):
p=self.next
while p is not None:
print(p.data)
p=p.next
class MyStack():
def __init__(self):
self.elemStack=Stack()#用来储存栈
self.minStack=Stack()#用来保存栈中的最小值，当前栈的最小值即为栈顶元素
#压栈
def push(self,item):
"""
若当前元素的值比比minStack的栈顶元素小，或者“相等”！！都入栈
这里是重点，网上很多文章，他们用的Java写的，但是同样没注意到这点！
他们都只注意到当前元素要比minStack栈顶元素小，没注意到相等的情况。如果栈elemStack中为1-2-3-1-2-4，则minStack为：1-2-3-4(栈顶在前)，如果第一个1出栈，则elemStack:2-3-1-2-4,minStack:2-3-4,显而易见，最小值为1，但是minStack栈顶为2，所以出错了！！！！！！
很多教材，和网上文章都没注意到。
"""
#先判断
if self.minStack.isEmpty():
return self.elemStack.push(item), self.minStack.push(item)
if item<=self.minStack.top():
#相等或小于，都入栈
return self.elemStack.push(item),self.minStack.push(item)
else:
#大于,只存储在elemstack
return self.elemStack.push(item)
def pop(self):
"""
如果elemStack的栈顶元素等于minStack的栈顶元素，则两个都弹栈，如果elemStack的栈顶元素大于minStack的栈顶元素，则只有elemStack弹栈
"""
if self.elemStack.top()==self.minStack.top():
return self.elemStack.pop(),self.minStack.pop()
else:
return self.elemStack.pop()
def minitem(self):
#返回最小值
return self.minStack.top()
if __name__ == '__main__':
s=MyStack()
s.push(4)
s.push(5)
s.push(7)
print("此时栈中的最小值为：",s.minitem())
s.push(3)
print("此时栈中的最小值为：",s.minitem())
s.push(5)
s.push(9)
print("此时栈中的最小值为：",s.minitem())
s.push(3)
print("此时栈中的最小值为：",s.minitem())
s.pop()
print("此时栈中的最小值为：",s.minitem())
加油！！
网友评论