定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
思路:栈stack保存数据,辅助栈assist保存依次入栈最小的数 stack中依次入栈,6,5,8,4,3,9 assist依次入栈,6,5,4,3 每次入栈的时候,如果入栈的元素比assist中的栈顶元素小或等于则入栈,否则不入栈。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = [] #数据栈
self.assist = [] #辅助栈
def push(self, node):
# write code here
min = self.min() #得到栈中元素的最小值
if min > node or not min: #若待入栈的元素值小于栈中最小值或栈为空时
self.stack.append(node) #将这个元素分别压入数据栈和辅助栈
self.assist.append(node)
else:
self.stack.append(node) #否则只将这个元素压入数据栈
def pop(self):
# write code here
if self.stack:
if self.stack[-1] == self.assist[-1]: #若数据栈和辅助栈的栈顶的元素值相等
self.stack.pop() #则分别将这两个栈的栈顶元素弹出
self.assist.pop()
else:
self.stack.pop() #否则只弹出数据栈的栈顶元素
def top(self):
# write code here
if self.stack:
return self.stack[-1] #返回数据栈的栈顶元素
def min(self):
# write code here
if self.assist:
return self.assist[-1] #返回辅助栈顶层元素,即最小值
Stack<Integer> stackTotal = new Stack<Integer>();
Stack<Integer> stackLittle = new Stack<Integer>();
public void push(int node) {
stackTotal.push(node);
if(stackLittle.empty()){
stackLittle.push(node);
}else{
if(node <= stackLittle.peek()){
stackLittle.push(node);
}else{
stackLittle.push(stackLittle.peek());
}
}
}
public void pop() {
stackTotal.pop();
stackLittle.pop();
}
public int top() {
return stackTotal.peek();
}
public int min() {
return stackLittle.peek();
}