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

简介: 问题描述问题分析算法描述性能分析代码实现

问题描述


 如何在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<Integer> stack = new Stack<>();// 存储栈
    private Stack<Integer> minStack = new Stack<>();// 最小值辅助栈
    private Stack<Integer> 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<int> stacks;// 存储栈
    stack<int> minStack;// 最小值辅助栈
    stack<int> maxStack;// 最大值辅助栈
};


————————————————

版权声明:本文为CSDN博主「Acx7」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/Acx77/article/details/116853827

相关文章
|
1天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
12 5
|
1天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
|
1天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
6天前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解(递归+记忆化搜索)
**NOIP2003普及组栈问题**:给定操作数序列1到n,仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3,输出5。当队列空时返回1,栈空则只能入栈,栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
9 1
|
8天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
8 1
|
11天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
18 4
|
11天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
20小时前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
3 0
|
1天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
1天前
|
存储 算法 编译器
【数据结构与算法】使用数组实现栈:原理、步骤与应用
【数据结构与算法】使用数组实现栈:原理、步骤与应用