【Leetcode】【Easy】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.

实现一个栈的基本功能，并且可以用o(1)的时间取出栈的最小元素。

使用两个栈的解题方法：

建立两个栈容器，一个常规使用elementStack，一个保存栈内最小元素minStack。

注意：

常规栈中最小的元素可能不唯一。当某个最小元素出栈时，minStack也需做出出栈动作。因此minStack栈中记录最小元素的数量应该和elementStack中最小元素数量相同。

也就是，每次进行常规栈压栈时，都进行和min栈记录的最小元素比较，将小于等于min栈最小元素的常规元素压栈。

代码：

 class MinStack {

 public:

     void push(int x) {

         element.push(x);

         if (min.empty() || x <= min.top())

             min.push(x);

     }

     void pop() {

         if (!element.empty()) {

             if (element.top() == min.top())

                 min.pop();

             element.pop();

         }

     }

     int top() {

         if (!element.empty())

             return element.top();

     }

     int getMin() {

         if (!min.empty())

             return min.top();

     }

 private:

     stack<int> element;

     stack<int> min;

 };

也可以只使用一个栈，即常规栈。只是压栈的每个元素都包含当前栈内最小元素值。

即，假设当前栈内最小值为m，当对元素A压栈时，若A<=m，则压入 (A, A)，若A>m，则压入 (A, m)。

（代码略）

附录：

各种数据结构最简洁表示方法，参考《数据结构与算法分析—C语言版》

巴特西

【Leetcode】【Easy】Min Stack

最新文章

热门文章