题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：
1 可以考虑每次比较进栈元素，使用固定单元将最小的元素存起来 这样不能获得次小元素
2 空间换时间 创建一个辅助栈将每次栈中的最小元素压入辅助栈中
package new_offer;
/**
* 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数
* （时间复杂度应为O（1））。
* 思路：借助一个辅助栈，将每次栈中的最小元素压入辅助栈中。
* smin每次进栈元素为当前栈中的最小元素。
*/
import java.util.Stack;
public class N20_Stack_Min {
public class Solution {
//定义一个数据栈及一个辅助栈
Stack<Integer> sdata=new Stack();
Stack<Integer> smin=new Stack();
public void push(int node) {
sdata.push(node);
if(smin.size()==0||smin.peek()>node) {
smin.push(node);
}else {
smin.push(smin.peek());
}
}
public void pop() {
if(sdata.size()>0&&smin.size()>0) {
sdata.pop();
smin.pop();
}
}
public int top() {
int n=sdata.peek();
return n;
}
public int min() {
return smin.peek();
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
转载于:https://www.cnblogs.com/kexiblog/p/11121214.html
