栈系列之 最小栈的实现

算法专题导航页面

【算法专题 - 栈】

1. 《栈系列之 栈排序》
2. 《栈系列之 最小栈的实现》
3. 《栈系列之 用栈实现队列》
4. 《栈系列之 递归实现一个栈的逆序》

【题目】
  设计一个栈，其拥有常规的入栈、出栈操作外，需要额外具备获取最小元素的功能。

【其他限制】
  获取最小元素功能的时间复杂度O(1)。

【图示】
  给定一个无序整数序列： 3, 8, 5, 6, 9, 1, 0, 2.

【分析】
1. 是否可以利用众所周知的栈结构及其入栈、出栈特性
    答案是肯定的，现在的问题在于单靠一个栈结构是无法实现获取最小元素功能。
2. 算法时间复杂度和空间复杂度衡量？
    题目要求的O(1)时间复杂度已是最优，同时也表明该算法需要采用空间换时间策略。在O(1)时间复杂度获取一个序列极值的数据结构：有序数组，哈希表，最大(小)堆。
    我们可以尝试构造上面提及的三种数据结构来实现最小元素获取功能，但这个“构造的过程”明显会引入额外的时间复杂度。

【解决方案】
    基于上述两方面分析，结合元素进栈/出栈操作，这里我们尝试采用一个辅助栈(MinStack)配合原始栈(MainStack)实现算法需要的新特性。其时间复杂度为O(1)，空间复杂度为O(n)。
    一个元素压入原始栈时，条件性压入辅助栈（目的是保存当前原始栈中值最小的元素）；元素弹出原始栈时，同样需要条件性弹出辅助栈的栈顶元素（目的是确保辅助栈的栈顶元素是当前原始栈中值最小的元素）。

• 元素进栈操作

1. 辅助栈MinStack为空。
   元素首先压入原始栈MainStack，而后直接压入辅助栈MinStack。
2. 辅助栈MinStack非空。
   元素首先压入原始栈MainStack，而后判断该元素是否需要压入辅助栈MinStack。
   此时分以下两种情况：
       a. 新入栈元素大于等于辅助栈栈顶元素。该元素不会被压入辅助栈。
       b. 新入栈元素小于辅助栈栈顶元素。该元素需要被压入辅助栈。
   此处有一个细节需要注意：入栈操作过程中及完成后，辅助栈中元素自底向上是一个递减序列。
   具体分析请看下面图解：
   (1) 元素3压入原始栈，此时辅助栈为空，故需要同时将其压入辅助栈。后续元素8, 5, 6, 9压入原始栈时，辅助栈不会有任何入栈操作。
   
   (2) 元素1压入原始栈，此时辅助栈非空。元素1小于辅助栈栈顶元素3，故元素1需要同时压入辅助栈。
   
   (3) 元素0压入原始栈，此时辅助栈亦非空。元素0小于辅助栈栈顶元素1，故元素0需要同时压入辅助栈。
   
   最后，尾元素2压入原始栈，因其大于辅助栈栈顶元素0，故无需压入辅助栈。至此算法的入栈操作完成。

• 元素出栈操作
  出栈操作相对简单：首先弹出原始栈的栈顶元素，当该栈顶元素等于辅助栈的栈顶元素时，弹出辅助栈的栈顶元素，以此来保证辅助栈的栈顶元素永远是原始栈当前元素中最小的元素。

【代码实现 - Java 精简版】

/*
 * DESC:
 * Java
 * A class implements function that can obtain the least element
*/ 
public class EnhancedStack {
    private Stack<Integer> mainStack;
    private Stack<Integer> minStack;
    public EnhancedStack() {
        this.mainStack = new Stack<Integer>();
        this.minStack = new Stack<Integer>();
    }

    // Push an element to stack EnhancedStack
    public void pushAction(int element) {
        this.mainStack.push(element);
        if (this.minStack.isEmpty() || (!this.minStack.isEmpty() && element < this.minStack.peek()))
            this.minStack.push(element)
    }

    // Pop an element from stack EnhancedStack
    public int popAction() {
        if (this.mainStack.IsEmpty())
            throw new RuntimeException("The stack is empty, please check!");
        int val = this.mainStack.pop();
        if (val == this.minStack.peek())
            this.minStack.pop();
        return val;
    }
    // Get the least element of current stack EnhancedStack
    public int getMinElement() {
        if (this.minStack.IsEmpty())
            thrown new RuntimeException("The stack is empty, please check!");
        return this.minStack.peek();
    }
}

【代码实现 - CPP 可运行版】

[输入描述]
第一行输入一个整数N，表示对栈进行的操作总数。
下面N行每行输入一个字符串S，表示操作的种类。
如果S为"push"，则后面还有一个整数X表示向栈里压入整数X。
如果S为"pop"，则表示弹出栈顶操作。
如果S为"getMin"，则表示询问当前栈中的最小元素是多少。

[输出描述]
对于每个getMin操作，输出一行表示当前栈中的最小元素是多少。
示例1
输入:

6
push 3
push 2
push 1
getMin
pop
getMin

输出:

1
2
[备注]
1<=N<=1000000
-1000000<=X<=1000000

//C++11(clang++ 3.9)

#include<iostream>
#include<stack>

using namespace std;

/*
* DESC:
* A enhanced stack that can get its minal element easily
*/
class EnhancedStack{
public:
   EnhancedStack(){}
   ~EnhancedStack(){}

   void pushAction(int element) {
       // push new element to the mainStack each time, but do the same to minStack conditionity
       mainStack.push(element);
       if (minStack.empty()|| element < minStack.top()) {
           minStack.push(element);
       } else {
           // push the top element to itself, this step will keep the size of two stacks' elements algin
           minStack.push(minStack.top());
       }
   }

   void popAction() {
       if (mainStack.empty()) {
           throw out_of_range("The stack is empty, please check!\n");
       } else {
           // based on the pushAction operation, here we just pop for both stacks simply 
           mainStack.pop();
           minStack.pop();
       }
   }

   int getMinElement() {
       if (minStack.empty()) {
           throw out_of_range("The stack is empty, please check!\n");
       } else {
           return minStack.top();
       }
   }

private:
   stack<int> mainStack;
   stack<int> minStack;
};


int main() {
   // new a EnhancedStack object
   EnhancedStack eStack;
   
   // define vars for input
   int stackSize = 0;
   string cmdStr;
   int element = 0;
   
   cin >> stackSize;
   while(stackSize --) {
       cin >> cmdStr;
       if ("push" == cmdStr) {
           cin >> element;
           eStack.pushAction(element);
       } else if ("getMin" == cmdStr) {
           cout << eStack.getMinElement() <<endl;
       } else {
           eStack.popAction();
       }
   }
   return 0;
}