老题目了，带有min函数的stack。
基本思想是，按照进栈顺序来扫一遍的话，min值并不是一直在变化的，可能连着过了好多个元素，min并没有变。形式化地说，若令f(j) = min(arr[1..j])，那么f(j)的图像由若干条阶跃相连的水平线段组成。因此f(j)可以将每一条线段压缩到一个元素。
基本操作是：用两个栈，除了正常的stack之外，附加一个min-stack，保存当前的最小值。
数据栈压入元素时，如果小于min-stack最小值，则表明f(j)出现了一个阶跃（从左向右开始了一根新的水平线），要记录下来；否则只压到数据栈即可。
数据弹出的时候，检查是不是min-stack的栈顶元素，如果等于则表示回退过程中要经历阶跃了（从右到左回退到之前的某根水平线），min-stack也出栈。
代码略。
性能分析：进栈出栈都是O(1)的，额外开销就是额外的空间。如果整个序列的最小元素最早进栈（譬如是一个递增序列进栈），这是最理想的了，O(1)的额外空间；如果是一个逆序的序列，就窘了，要一倍的额外空间。