当前位置：首页 > article >正文

leetcode155.最小栈，两个栈

article 2024/9/23 0:40:46

leetcode155.最小栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例：
MinStack minStack

题目分析

题目要求：实现一个栈，支持普通栈的操作，并且可以在O(1)时间复杂度内获取栈中的最大值。
算法应用：使用两个栈，一个用于存储所有元素（dataStack），另一个用于存储最大值（maxStack）。

算法步骤

初始化：创建两个空栈 dataStack 和 maxStack。
入栈（push）：
- 将元素压入 dataStack。
- 如果 maxStack 为空或新元素大于等于 maxStack 的栈顶元素，则也将新元素压入 maxStack。
出栈（pop）：
- 从 dataStack 弹出元素。
- 如果弹出的元素等于 maxStack 的栈顶元素，则也从 maxStack 弹出元素。
获取栈顶元素（top）：直接返回 dataStack 的栈顶元素。
获取最大值（getMax）：直接返回 maxStack 的栈顶元素。

算法流程

算法代码

class MinStack {
private:
    stack<int> dataStack;
    stack<int> minStack;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        if(minStack.empty() || x<=minStack.top()) minStack.push(x);
        dataStack.push(x);
    }
    
    void pop() {
        if(minStack.top()==dataStack.top()) minStack.pop();
        dataStack.pop();
    }
    
    int top() {
        return dataStack.top();
    }
    
    int min() {
        return minStack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */