包含 min 函数的栈
题目要求：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push、pop 的时间复杂度都是 O ( 1 ).
思路：
- 把每次的最小元素(之前的最小元素和新压入data栈的元素两者的较小值)存到辅助栈 mins 中
代码实现：
public class StackWithMin { // 数据栈 private List data = new ArrayList<>(); // 辅助最小值栈 private List 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 data = new ArrayList<>(); // 辅助最小值栈 private List 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); }}复制代码