lintcode面试题30：带最小值操作的栈_小林code 面试

实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。
你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。
样例
如下操作：push(1)，pop()，push(2)，push(3)，min()， push(1)，min() 返回 1，2，1

注意：lintcode上pop（）函数也要有返回值；

思路：

把每次的最小元素（数据栈之前最小的元素与新压入栈元素之间的较小值）存入辅助栈。保证辅助栈顶一直都是数据栈的最小元素。
当最小元素从数据栈内被弹出，同时弹出辅助栈栈顶元素，此时辅助栈栈顶的新元素就是下一个最小值。

代码：

void push(int number) {
        // write your code here
        data_stack.push(number);
        if(min_stack.size()==0||number<min_stack.top())
            min_stack.push(number);
        else
            min_stack.push(min_stack.top());
    }

    /*
     * @return: An integer
     */
    int pop() {
        // write your code here
        assert(data_stack.size()>0&&min_stack.size()>0);
        min_stack.pop();
        int temp = data_stack.top();//pop会删除栈顶元素，若需要返回栈顶元素需要先将栈顶元素存为变量
        data_stack.pop();
        return temp;
    }

    /*
     * @return: An integer
     */
    int min() {
        // write your code here
        assert(data_stack.size()>0&&min_stack.size()>0);
        return min_stack.top();
    }
private:
    stack <int>data_stack;
    stack <int>min_stack;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

知识点：

c++栈的方法的基本用法：
push(): 向栈内压入一个成员；
pop(): 从栈顶弹出一个成员；
top(): 返回栈顶，但不删除成员；
size(): 返回栈内元素的大小；
empty(): 如果栈为空返回true，否则返回false；

assert()；如果它的条件返回错误，则终止程序执行