题目要求：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push、pop 的时间复杂度都是 O ( 1 ).
思路：
- 把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)存到辅助栈 mins 中
代码实现：
public class StackWithMin {
// 数据栈
private List<Integer> data = new ArrayList<>();
// 辅助最小值栈
private List<Integer> mins = new ArrayList<>();
/**
* 思路 1 ：把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)存到辅助栈 mins 中
*
* 时间复杂度：O (1)
* 空间复杂度：O (n)
*/
private void push1(int num) throws Exception {
data.add(num);
if(mins.size() == 0) {
// 初始化mins
mins.add(num);
} else {
// 辅助栈mins每次push当前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时两栈同步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);
}
}
测试代码：
@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 栈中getMin1为：" + min1);
}
- 把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)的索引存到辅助栈 mins 中，每次在data栈中 getMin 的时候比较其索引值与 mins 中存的索引值是否相等，是则出栈。
public class StackWithMin {
// 数据栈
private List<Integer> data = new ArrayList<>();
// 辅助最小值栈
private List<Integer> mins = new ArrayList<>();
/**
* 思路 2 ：把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)的索引存到辅助栈 mins 中，
* 每次在data栈中 getMin 的时候比较其索引值与 mins 中存的索引值是否相等，是则出栈
*
* 时间复杂度：O (1)
* 空间复杂度 ：< 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 时先获取索引
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 通过 mins 栈中最小值的索引得到 data 栈中对应的值
* @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 栈中getMin为：" + min);
}
}
