牛客网剑指offer第20题——定义栈的数据结构

题目：

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

先上代码：

 1 class Solution {
 2   private:
 3         vector<int> stack;
 4         vector<int> minval; //用一个数无法完成最小值为O（n）,必须用一个序列对其进行存储
 5 public:
 6     void push(int value) {  //需要同时对最小元素和最大元素进行入栈出栈操作
 7         stack.push_back(value);
 8         if(stack.size() == 1)
 9             minval.push_back(value);
10         else 
11         {
12             if(minval.back() > top())
13                 minval.push_back(top());
14             else 
15                 minval.push_back(minval.back());
16         }
17     }
18     void pop() {          //
19         if(stack.size())
20         {
21             stack.pop_back();
22             //if(minval > top())
23                 minval.pop_back();
24         }
25     }
26     int top() {
27         if(stack.size())
28             return stack.back();
29     }
30     int min() {
31         if(stack.size())
32             return minval.back();//返回索引数组
33     }
34         
35 };

思路：既然要实现栈的数据结构，所以自然我们不能使用自带的栈去实现了吧，这里我们采用数组的方式实现。

这个题的难点在于：使用O(1)时间复杂度的方式实现min()函数，我们所应该认识到的是：找最小值意味着要进行比较，那么如果我们不采用缓存机制，我们是没有办法实现O(1)时间复杂度的。开始的时候，我试图只用一个int型变量试图存放当前状态下的最小值，后来发现这根本是不可能实现的。我们必须用另外一个数组空间也模拟一个栈，来动态维护当前数据栈中的最小值。我们需要清楚的是：当原数组构成的栈进行push和pop的时候，这个最小值状态栈必然也会动态的发生变化，我们只需要取其索引即可。

下面给出一些在上述代码中vector中用到的函数；

back()，返回数组的最后一个元素

pop_back()，删除数组的最后一个元素。