本題來自程序員代碼面試指南
- 設(shè)計(jì)一個(gè)有g(shù)etMin功能的棧
實(shí)現(xiàn)一個(gè)特殊的棧，在實(shí)現(xiàn)棧的基本功能的基礎(chǔ)上，再實(shí)現(xiàn)返回棧中最小元素的操作盲厌。 - 要求
- pop馒过、push臭脓、getMin操作的時(shí)間復(fù)雜度都是O (1)。
- 設(shè)計(jì)的棧類型可以使用現(xiàn)成的棧結(jié)構(gòu)腹忽。
- 解決方法
倆個(gè)棧来累，一個(gè)是普通棧里面放數(shù)據(jù)，另一個(gè)棧里面放棧中最小值
- 第一種方法在壓棧時(shí)判斷插入時(shí)為空椌阶啵或者元素小于等于當(dāng)前棧頂元素,壓入最小值棧中嘹锁。
如果彈棧元素大小等于（不可能小于）最小值棧頂元素，同時(shí)從最小值棧中彈出着裹。 - 第二種方法插入的元素比當(dāng)前棧中最小值大领猾，將最小值重復(fù)入棧。
彈棧時(shí)同時(shí)彈出數(shù)據(jù)棧和最小值棧中的一個(gè)元素骇扇。
第二種方法和第一種的區(qū)別就是第一種數(shù)據(jù)棧和最小值棧里的數(shù)據(jù)量是不相等的摔竿，在彈棧時(shí)要判斷彈出的元素是否和最小值棧棧頂元素相等，第二種方法只要彈棧就同時(shí)從最小值棧里彈出一個(gè)
public class Mystack1 implements Mystack{
private Stack<Integer> stackData;//存儲(chǔ)數(shù)據(jù)的棧與正常棧功能相同
private Stack<Integer> stackMin;//保存每一步的最小值
public Mystack1() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
/**
* 壓棧操作
*
* @param newNum
*/
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
//最小值的棧是空的直接壓入
this.stackMin.push(newNum);
} else if (newNum <= stackMin.peek()) {
//插入元素小于等于當(dāng)前棧頂元素,也壓入棧中
this.stackMin.push(newNum);
}
//數(shù)據(jù)壓入數(shù)據(jù)棧
this.stackData.push(newNum);
}
/**
* 彈棧操作
*
* @return
* @throws Exception
*/
public int pop() throws Exception {
//椊程猓空報(bào)錯(cuò)
if (this.stackData.isEmpty()) {
throw new Exception("椪兀空，無數(shù)據(jù)返回");
}
int pop = this.stackData.pop();
//如果彈棧元素大小等于最小值棧頂元素韭山，同時(shí)從最小值棧中彈出
if (pop == this.stackMin.peek()) {
this.stackMin.pop();
}
return pop;
}
/**
* 返回棧中最小的元素的值
*
* @return
* @throws Exception
*/
public int getMin() throws Exception {
if (this.stackMin.isEmpty()) {
//最小值椨艏荆空報(bào)錯(cuò)
throw new Exception("椑淅＃空");
}
return this.stackMin.peek();
}
}
public class Mystack2 implements Mystack{
private Stack<Integer> stackData;//存儲(chǔ)數(shù)據(jù)的棧與正常棧功能相同
private Stack<Integer> stackMin;//保存每一步的最小值
public Mystack2() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
/**
* 壓棧操作
*
* @param newNum
*/
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
//最小值的棧是空的直接壓入
this.stackMin.push(newNum);
} else if (newNum <= stackMin.peek()) {
//插入元素小于等于當(dāng)前棧頂元素,也壓入棧中
this.stackMin.push(newNum);
} else {
//插入的元素比當(dāng)前棧中最小值大，將最小值重復(fù)入棧
this.stackMin.push(this.stackMin.peek());
}
//數(shù)據(jù)壓入數(shù)據(jù)棧
this.stackData.push(newNum);
}
/**
* 彈棧操作
*
* @return
* @throws Exception
*/
public int pop() throws Exception {
//椕瘟眩空報(bào)錯(cuò)
if (this.stackData.isEmpty()) {
throw new Exception("椝普恚空，無數(shù)據(jù)返回");
}
//同時(shí)彈出數(shù)據(jù)棧和最小值棧中的一個(gè)元素
int pop = this.stackData.pop();
this.stackMin.pop();
return pop;
}
/**
* 返回棧中最小的元素的值
*
* @return
* @throws Exception
*/
public int getMin() throws Exception {
if (this.stackMin.isEmpty()) {
//最小值椖昴空報(bào)錯(cuò)
throw new Exception("椩浼撸空");
}
return this.stackMin.peek();
}
}
性能測試
循環(huán)一千萬次發(fā)現(xiàn)第二種方法的運(yùn)算時(shí)間上要少于第一種算法，這大概就是空間換時(shí)間吧
最后附上github地址
