面试金典题3.2

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

class MinStack {
public:
    //定义两个栈，一个用于存储元素，一个用于存最小值
    stack<int> mystack;
    stack<int> minstack;
    /** initialize your data structure here. */
    //先将最大值入最小值的栈，方便第一个比较
    MinStack() {
         minstack.push(INT_MAX);
    }
    //同时将元素加入两个栈
    void push(int x) {
        mystack.push(x);
        //比较入栈元素和当前栈顶元素，将最小值入栈
        minstack.push(min(x,minstack.top()));
    }
    //同时让两个栈的栈顶元素出栈
    void pop() {
        mystack.pop();
        minstack.pop();
    }
    //返回栈顶元素
    int top() {
        return mystack.top();
    }
    //返回最小栈的栈顶元素，即当前栈中的最小值
    int getMin() {
        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->getMin();
 */

这道题的思路很简单，就是同时定义两个栈，一个存储元素，一个存储当前栈中最小值。因此最小栈的栈顶元素永远是当前栈中的最小元素。

原文地址：https://blog.csdn.net/m0_73096516/article/details/142668671

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！