本文共 3498 字，大约阅读时间需要 11 分钟。

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数

在该栈中，调用min、push及pop德尔时间复杂度都是O(1)

思路：

1. 在栈中定义一个标识最小变量的变量 每次入栈的时候进行比较判断 保证该变量保存的始终是入栈元素中的最小值 出现问题：如果该最小元素出栈？ 2. 使用一个栈保存入栈的数据元素，再使用一个栈辅助保存最小值 以及定义一个变量表示当前还在栈中所有元素的最小值 [默认-1] 当有元素入栈时 1. 判断栈是否为空 如果栈为空的话 那么直接将该元素入数据栈和辅助栈，最小变量表示为当前元素 2. 在栈不为空的情况下 则要进行判断 如果当前入栈元素小于当前栈中的最小值 那么将最小标识变量的值设置为当前入栈元素，将当前元素入数据栈和辅助栈

如果当前元素大于最小标识变量的值，则将当前元素入数据栈，最小标识变量的值入辅助栈，最小标识变量的值不变

代码

package com.hqq.exercise.stack_queue;import java.util.Stack;/** * MinStack 包含min函数的栈 * 题目描述: * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数 * 在该栈中，调用min、push及pop德尔时间复杂度都是O(1) * 思路: * 定义一个辅助栈和一个标识最小值的变量 * 当一个数入栈时,将最小值也同时入栈 * Created by heqianqian on 2017/8/13. */public class MinStack {
       //数据栈    private Stack
   
     dataStack = new Stack<>();    //辅助栈    private Stack
    
      assStack = new Stack<>();    //最小值    private int min;    public void push(Integer num) {        if (dataStack.isEmpty()) {
  //当栈为空时            min = num;            assStack.push(num);        } else {
  //栈不为空时 进行比较            if (num < min) {
  //如果当前入栈元素最小的话                min = num;                assStack.push(num);            } else {                assStack.push(min);            }        }        dataStack.push(num);    }    public Integer pop() {        assStack.pop();        if (!assStack.empty()) {            min = assStack.peek();        }else{            min = -1;        }        return dataStack.pop();    }    public Integer min() {        return min;    }    public boolean isEmpty() {        return dataStack.isEmpty();    }    public void printDataStack() {        int size = dataStack.size();        System.out.print("数据栈: ");        for (int i = 0; i < dataStack.size(); i++) {            System.out.print(dataStack.get(i) + " ");        }        System.out.println();    }    public void printAssistStack() {        int size = assStack.size();        System.out.print("辅助栈: ");        for (int i = 0; i < assStack.size(); i++) {            System.out.print(assStack.get(i) + " ");        }        System.out.println();    }    public void printMin() {        System.out.println("最小值: " + min);    }}
    
   

package com.hqq.exercise.stack_queue;import com.hqq.BaseTest;import com.hqq.exercise.tree.MirrorTree;import org.junit.Before;import org.junit.Test;import static org.junit.Assert.*;/** * MinStack 包含min函数的栈 * 题目描述: * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数 * 在该栈中，调用min、push及pop德尔时间复杂度都是O(1) * 思路: * 定义一个辅助栈和一个标识最小值的变量 * 当一个数入栈时,将最小值也同时入栈 * 样例输入: * {3,4,2,1} * Created by heqianqian on 2017/8/13. */public class MinStackTest extends BaseTest{
       private int[] data;    @Override    @Before    public void setUp() throws Exception {        super.setUp();        data = new int[]{
  3,4,2,1};    }    @Test    public void testMinStack() throws Exception {        MinStack minStack = new MinStack();        for (int i = 0; i < data.length; i++) {            System.out.println("压入:"+data[i]);            minStack.push(data[i]);            minStack.printDataStack();            minStack.printAssistStack();            minStack.printMin();        }        while (!minStack.isEmpty()){            System.out.println("弹出:"+minStack.pop());            minStack.printDataStack();            minStack.printAssistStack();            minStack.printMin();        }    }}

输出结果

压入:3数据栈: 3 辅助栈: 3 最小值: 3压入:4数据栈: 3 4 辅助栈: 3 3 最小值: 3压入:2数据栈: 3 4 2 辅助栈: 3 3 2 最小值: 2压入:1数据栈: 3 4 2 1 辅助栈: 3 3 2 1 最小值: 1弹出:1数据栈: 3 4 2 辅助栈: 3 3 2 最小值: 2弹出:2数据栈: 3 4 辅助栈: 3 3 最小值: 3弹出:4数据栈: 3 辅助栈: 3 最小值: 3弹出:3数据栈: 辅助栈: 最小值: -1