題目描述
????自定義一個(gè)棧結(jié)構(gòu)箱熬，包含push(),pop(),和getMin()三個(gè)函數(shù)沽瞭，getMin用于獲取棧中數(shù)據(jù)的最小值提针，要求時(shí)間復(fù)雜度均為O(1)。
思路分析
????拿到這個(gè)題目可能首先想到的是土匀，定義一個(gè)輔助變量記錄當(dāng)前狀態(tài)下的最小值，但是如果最小值被彈出了怎么辦呢形用？我們無(wú)法在O(1)時(shí)間復(fù)雜度下找到新的最小值就轧。因此我們可以考慮定義一個(gè)輔助棧，同步存下每個(gè)狀態(tài)下的最小值尾序。以空間換時(shí)間钓丰，這是算法設(shè)計(jì)中最常見(jiàn)的思想！
Java代碼實(shí)現(xiàn)
import java.util.Stack;
/**
* 實(shí)現(xiàn)一個(gè)棧每币，包含pop,push以及函數(shù)min獲取棧中的最小值携丁，時(shí)間復(fù)雜度均為O(1)
* @author Administrator
* @version 2018/10/12
*/
public class Exe32_StackWithMin {
public static void main(String[] args) {
MyStack testStack=new MyStack();
testStack.push(1.0);
testStack.push(2.0);
testStack.push(1.5);
testStack.push(3.0);
System.out.println("the min value is "+testStack.getMin());
System.out.println("the top value is "+testStack.pop());
}
}
class MyStack{
//數(shù)據(jù)棧
Stack<Double> dataStack=new Stack<Double>();
//最小值棧
Stack<Double> minStack=new Stack<Double>();
public synchronized void push(Double data) {
dataStack.push(data);
if(minStack.isEmpty()){
minStack.push(data);
}else {
minStack.push(Math.min(minStack.peek(), data));
}
}
public synchronized Double pop() {
if(dataStack.isEmpty()||minStack==null){
return null;
}else {
if(minStack.pop()!=null){
return dataStack.pop();
}else {
return null;
}
}
}
public synchronized Double getMin() {
if(minStack.isEmpty()){
return null;
}else {
return minStack.peek();
}
}
}
