題目要求：定義棧的數(shù)據(jù)結(jié)構(gòu)饥悴，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的 min 函數(shù)。在該棧中瓣铣，調(diào)用 min贷揽、push、pop 的時(shí)間復(fù)雜度都是 O ( 1 ).
思路：
- 把每次的最小元素(之前的最小元素和新壓入data棧的元素兩者的較小值)存到輔助棧 mins 中
代碼實(shí)現(xiàn)：
public class StackWithMin {
// 數(shù)據(jù)棧
private List<Integer> data = new ArrayList<>();
// 輔助最小值棧
private List<Integer> mins = new ArrayList<>();
/**
* 思路 1 ：把每次的最小元素(之前的最小元素和新壓入data棧的元素兩者的較小值)存到輔助棧 mins 中
*
* 時(shí)間復(fù)雜度：O (1)
* 空間復(fù)雜度：O (n)
*/
private void push1(int num) throws Exception {
data.add(num);
if(mins.size() == 0) {
// 初始化mins
mins.add(num);
} else {
// 輔助棧mins每次push當(dāng)前data中的最小值
int min = getMin1();
if (num >= min) {
mins.add(min);
} else {
mins.add(num);
}
System.out.print("push1完后mins棧中的值為：");
for (int index : mins) {
System.out.print(index + " ");
}
}
}
private int pop1() throws Exception {
// 棻途龋空循捺，異常雄人，返回-1
if(data.size() == 0) {
throw new Exception("Stack is Empty!");
}
// pop時(shí)兩棧同步pop
mins.remove(mins.size() - 1);
System.out.print("pop1完后mins棧中的值為：");
for (int index : mins) {
System.out.print(index + " ");
}
return data.remove(data.size() - 1);
}
private int getMin1() throws Exception {
// 棧空恰力，異常旗吁，返回-1
if(mins.size() == 0) {
throw new Exception("Stack is Empty!");
}
// 返回mins棧頂元素
return mins.get(mins.size() - 1);
}
}
測(cè)試代碼：
@Test
public void testStackWithMin() throws Exception {
StackWithMin stackWithMin1 = new StackWithMin();
/* 思路 1 */
stackWithMin1.push1(6);
stackWithMin1.push1(2);
stackWithMin1.push1(2);
System.out.println();
int pop1 = stackWithMin1.pop1();
System.out.print("data 棧中pop1的元素：" + pop1);
System.out.println();
int min1 = stackWithMin1.getMin1();
System.out.print("data 棧中g(shù)etMin1為：" + min1);
}
- 把每次的最小元素(之前的最小元素和新壓入data棧的元素兩者的較小值)的索引存到輔助棧 mins 中很钓，每次在data棧中 getMin 的時(shí)候比較其索引值與 mins 中存的索引值是否相等翻具，是則出棧回还。
public class StackWithMin {
// 數(shù)據(jù)棧
private List<Integer> data = new ArrayList<>();
// 輔助最小值棧
private List<Integer> mins = new ArrayList<>();
/**
* 思路 2 ：把每次的最小元素(之前的最小元素和新壓入data棧的元素兩者的較小值)的索引存到輔助棧 mins 中柠硕，
* 每次在data棧中 getMin 的時(shí)候比較其索引值與 mins 中存的索引值是否相等运提，是則出棧
*
* 時(shí)間復(fù)雜度：O (1)
* 空間復(fù)雜度 ：< O (n)
*/
private void push(int num) throws Exception {
data.add(num);
if (mins.size() == 0) { // 初始化 mins 棧
mins.add(0);
} else {
// mins 輔助棧push最小值的索引
int minValue = getMin();
if (num < minValue) {
mins.add(data.size() - 1); // 將最小值在data棧中的索引 push 到 mins 棧中
}
System.out.print("push完后mins棧中的索引為：");
for (int index : mins) {
System.out.print(index + " ");
}
}
}
private int pop() throws Exception {
// 棧為空民泵，則拋出異常
if (data.size() == 0) {
throw new Exception("stack is empty!");
}
// pop 時(shí)先獲取索引
int popIndex = data.size() - 1;
// 獲取 mins 輔助棧頂元素，它是最小值索引
int minIndex = mins.get(mins.size() - 1);
// 若 pop 出去的索引就是最小值索引胁编，mins 才出棧
if (popIndex == minIndex) {
mins.remove(mins.size() - 1);
}
System.out.print("pop后mins棧中的索引為：");
for (int index : mins) {
System.out.print(index + " ");
}
return data.remove(data.size() - 1);
}
/**
*
* @return 通過(guò) mins 棧中最小值的索引得到 data 棧中對(duì)應(yīng)的值
* @throws Exception
*/
private int getMin() throws Exception {
// 棧為空鳞尔，則拋出異常
if (data.size() == 0) {
throw new Exception("stack is empty!");
}
// 獲取 mins 棧頂元素，它是最小值索引
int minIndex = mins.get(mins.size() - 1);
return data.get(minIndex);
}
@Test
public void testStackWithMin() throws Exception {
StackWithMin stackWithMin1 = new StackWithMin();
/* 思路 2 */
StackWithMin stackWithMin = new StackWithMin();
stackWithMin.push(6);
stackWithMin.push(2);
stackWithMin.push(2);
System.out.println();
int pop = stackWithMin.pop();
System.out.print("data 棧中pop的元素：" + pop);
System.out.println();
int min = stackWithMin.getMin();
System.out.print("data 棧中g(shù)etMin為：" + min);
}
}
