3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. 1. Stack1，push(), pop()时间复杂度:O(n) 2.Stack2,与Stack3,满
3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
1. Stack1，push(), pop()时间复杂度:O(n)
2.Stack2,与Stack3,满足要求，Stack3更优化，消除了部分冗余
3.堆栈特点，在当前元素为弹出时，当前元素的最小值不会改变
import java.util.Stack;
class Stack1{
private Node top = null;
private Node first = null;
class Node{
int val;
Node next;
Node min;
public Node(int val){
this.val = val;
this.next = null;
this.min = null;
}
}
//time complexity:O(n)
public void push(int val){
if(top != null){
Node n = new Node(val);
n.next = top;
top = n;
if(first.val s = new Stack<integer>();
class Node{
int val;
Node next;
public Node(int val){
this.val = val;
this.next = null;
}
}
public void push(int val){
if(top != null){
Node n = new Node(val);
n.next = top;
top = n;
if(s.peek() >= val)
s.push(val);
}else{
top = new Node(val);
s.push(val);
}
}
public int pop(){
if(top != null){
Node n = top;
top = top.next;
if(n.val == s.peek())
s.pop();
return n.val;
}else
return Integer.MIN_VALUE;
}
public int min(){
if(top == null)
return Integer.MAX_VALUE;
else
return s.peek();
}
public boolean empty(){
if(top == null)
return true;
else
return false;
}
}
public class Solution{
public static void main(String[] args){
int[] A = {
23, 11 , 12, 34, 10, 12, 7, 45, 21,
12, 6, 12, 5, 85, 4, 3, 2, 1
};
//test for Stack1
Stack1 stack1 = new Stack1();
for(int i=0;i <br>
<br>
</integer>
