LeetCode: 155. Min Stack

题目描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.

Example:

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

题目大意：设计一个支持 push, pop, top 操作，以及在常数时间内返回最小值的栈。

解题思路

用一个数组作为栈的内存，存储压入栈的元素。用另一个数组作为最小值栈的内存，栈顶存储当前数据栈当前最小值。

AC 代码

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        minStk.push_back(INT_MAX);
    }

    void push(int x) {
        stk.push_back(x);
        // 将 minStk 的栈顶和 x 的最小值压入 minStk,
        // 保证 minStk 栈顶永远是 stk 栈内元素的最小值
        minStk.push_back(min(minStk.back(), x));
    }

    void pop() {
        if(!stk.empty())
        {
            stk.pop_back();
            minStk.pop_back();
        }
    }

    int top() {
        return stk.back();
    }

    int getMin() {
        return minStk.back();
    }
private:
    vector<int> stk; // 存储栈的数据
    vector<int> minStk; // 存储最小值
};

/** * 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(); */