Java实现最小栈的实现

实现一个栈,该栈带有出栈(pop)、入栈(push)、取最小元素(getMin)3
个方法。要保证这3个方法的时间复杂度都是O(1)。

定义一个main变量,每进来一个最小的元素就进行赋值,在java中使用getMin方法过滤每个进栈的元素,找到最小的那个,每当进来一个新的元素都会和已经存在的值进行比较,如果小于当前栈内的最小值则对main变量进行赋值,如果大于则不做任何改变。

那么这种做法的话呢,显然不太好,因为只考虑了进栈场景,没有考虑出栈场景。

假设已经进展的元素有4,9,7,3;那么在第一次出栈的时候当前最小值出栈了,栈内已经没有之前最小值得记录了,这时的最小值变成了4,显然不是我们想要的结果。

接下来优化一下:

  1. 设原有的栈叫作栈A,此时创建一个额外的“备胎”栈B,用于辅助栈A。
  2. 当第1个元素进入栈A时,让新元素也进入栈B。这个唯一的元素是栈A的当
    前最小值。
  3. 之后,每当新元素进入栈A时,比较新元素和栈A当前最小值的大小,如果小
    于栈A当前最小值,则让新元素进入栈B,此时栈B的栈顶元素就是栈A当前最小值。
  4. 每当栈A有元素出栈时,如果出栈元素是栈A当前最小值,则让栈B的栈顶元
    素也出栈。此时栈B余下的栈顶元素所指向的,是栈A当中原本第2小的元素,代替刚
    才的出栈元素成为栈A的当前最小值。(备胎转正。)
  5. 当调用getMin方法时,返回栈B的栈顶所存储的值,这也是栈A的最小值。
    显然,这个解法中进栈、出栈、取最小值的时间复杂度都是O(1),最坏情况空
    间复杂度是O(n)。

代码实现的话如下:因为原本是借助漫画算法中的代码实现,但是实际运用还有一定的错误,有许多bug,包括运行不了,所以做了一些小的修改,这里我用的是jdk11.

import java.util.Stack;


class MinStack {
    private Stack<Integer> mainStack = new Stack<Integer>();
    private Stack<Integer> minStack = new Stack<Integer>();


    /**
     * 入栈操作
     *
     * @param element 入栈的元素
     */
    private void push(int element) {
        mainStack.push(element);
        // 如果辅助栈为空,或者新元素小于或等于辅助栈栈顶,则将新元素压入辅助栈
        if (minStack.empty() || element <= minStack.peek()) {
            minStack.push(element);
        }
    }

    /**
     * 出栈操作
     */
    private Integer pop() {
        // 如果出栈元素和辅助栈站定元素值相等,辅助栈出栈
        if (mainStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        return mainStack.pop();
    }

    /**
     * 获取栈的最小元素
     */
    private int getMin() throws Exception {
        if (mainStack.empty()) {
            throw new Exception("stack is empty");
        }
        return minStack.peek();
    }

    public static void main(String[] args) throws Exception {
        MinStack stack = new MinStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 专业考题类型管理运行工作负责人一般作业考题内容选项A选项B选项C选项D选项E选项F正确答案 变电单选GYSZ本规程...
    小白兔去钓鱼阅读 9,090评论 0 13
  • 题目: 实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。要保证这三个方法的时...
    zheting阅读 441评论 0 1
  • 栈:如何实现浏览器的前进和后退功能? 浏览器的前进、后退功能,我想你肯定很熟悉吧? 当你依次访问完一串页面 a-b...
    GhostintheCode阅读 927评论 0 2
  • 先来个简单的栈(先进后出) 题目:实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个...
    darklindj阅读 1,368评论 0 0
  • 郭相麟 在纪念雷峰精神的日子里,看到一些照片就看到了一个年轻生命鲜活的经历! 他当个农民,做个国家机关工作人员...
    郭相麟阅读 495评论 0 0