如何在O(1)时间复杂度获取栈中最大值和最小值-白红宇的个人博客

发布日期：2021-05-08 23:14:53 浏览次数：28 分类：博客文章

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

问题描述：

　　如何在O(1)时间复杂度获取栈中的最大值和最小值？

问题分析：

　　普通栈规定的push(入栈)、pop(出栈)、peek(查看栈顶)等操作都只能在栈顶上操作，如果栈中元素是有序的，那么我们就可以记录栈顶和栈底元素完成问题要求，但这是不可能的。普通栈不能解决问题，显然我们需要重新定义一种新的栈结构。能否在栈中定义两个变量min和max记录最小值和最大值呢，答案是否定的，因为并不是只有进栈操作，经过一系列出栈操作后，有可能最开始的最大值和最小值已经出栈。为了解决这个问题，我们就需要两个辅助栈记录栈的每个状态下的最大值和最小值。

算法描述：

　　定义一个minStack栈和一个maxStack栈，分别在栈顶保存当前栈内最小值和最大值，以minStack为例，每次有元素入栈，就与minStack的栈顶元素比较，若小于栈顶元素，则入栈成为新的栈顶元素，若大于栈顶元素，则入栈原先的栈顶元素，maxStack栈与上述思路相同。出栈时，三个栈都需要出栈。定义getMin与getMax函数分别返回minStack和maxStack栈顶元素，实现在O(1)时间复杂度获取栈中的最小值和最大值。

性能分析：

　　时间复杂度：O(1)　　

　　空间复杂度：O(N)

　　加入两个辅助栈实现O(1)时间复杂度获取栈中的最大值和最小值，典型的以空间换取时间。

代码实现：

// Java代码class MyStack {    public void push(int e) {// 新建MyStack数据结构的push函数        stack.push(e);// 元素入栈        // 判断是否需要更新minStack栈顶元素        if (minStack.isEmpty() || e < minStack.peek()) {            minStack.push(e);// 入栈元素更小，更换栈顶元素        } else if (e >= minStack.peek()) {            minStack.push(minStack.peek());// 不用更换栈顶元素        }        // 判断是否需要更新maxStack栈顶元素        if (maxStack.isEmpty() || e > maxStack.peek()) {            maxStack.push(e);// 入栈元素更大，更换栈顶元素        } else if (e <= maxStack.peek()) {            maxStack.push(maxStack.peek());// 不用更换栈顶元素        }    }    public int pop() {// 新建MyStack数据结构的pop函数        // 三栈全部出栈        int ret = stack.pop();        minStack.pop();        maxStack.pop();        return ret;    }    public int getMin() {// O(1)时间返回最小值        return minStack.peek();    }    public int getMax() {// O(1)时间返回最大值        return maxStack.peek();    }        private Stack
    
      stack = new Stack<>();// 存储栈    private Stack
     
       minStack = new Stack<>();// 最小值辅助栈    private Stack
      
        maxStack = new Stack<>();// 最大值辅助栈}

// C++代码class MyStack {public:    void push(int e) {// 新建MyStack数据结构的push函数        stacks.push(e);// 元素入栈        // 判断是否需要更新minStack栈顶元素        if (minStack.empty() || e < minStack.top()) {            minStack.push(e);// 入栈元素更小，更换栈顶元素        } else if (e >= minStack.top()) {            minStack.push(minStack.top());// 不用更换栈顶元素        }        // 判断是否需要更新maxStack栈顶元素        if (maxStack.empty() || e > maxStack.top()) {            maxStack.push(e);// 入栈元素更大，更换栈顶元素        } else if (e <= maxStack.top()) {            maxStack.push(maxStack.top());// 不用更换栈顶元素        }    }    void pop() {// 新建MyStack数据结构的pop函数        // 三栈全部出栈        stacks.pop();        minStack.pop();        maxStack.pop();    }    int top() {        return stacks.top();    }     int getMin() {// O(1)时间返回最小值        return minStack.top();    }    int getMax() {// O(1)时间返回最大值        return maxStack.top();    }    private:    stack
    
      stacks;// 存储栈    stack
     
       minStack;// 最小值辅助栈    stack
      
        maxStack;// 最大值辅助栈};

上一篇：小艾和她女朋友(俄罗斯农民乘法)

下一篇：冒泡排序(Bubble Sort)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章