程序员面试100题--02

题目描述：
实现一个min操作位O(1)的栈
//之前其实写过一次，这次换一个何海涛的方法，设定辅助栈保存当前的最小值的索引。 
1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <map>
 8 #include <vector>
 9 #include <list>
10 #include <stack>
11 using namespace std;
12 
13 /*
14 思路:
15 每次push的时候，同时push一个最小位置索引到辅助栈当中
16 */
17 
18 class minStack
19 {
20 public:
21     vector<int> data;
22     vector<int> minIndex;
23     
24     //push的时候判断当前元素和最小元素的关系。选择push到索引辅助栈的值
25     void push(const int &elem)
26     {
27         data.push_back(elem);
28         if(data.size() == 1)
29         {
30             minIndex.push_back(0);
31         }
32         else
33         {
34             int curMinIndex = minIndex[minIndex.size()-1];
35             if(data[curMinIndex] < elem)
36             {
37                 minIndex.push_back(curMinIndex);
38             }
39             else
40             {
41                 minIndex.push_back(minIndex.size()-1);
42             }
43         }
44     }
45     
46     //pop的时候，同时popminindex即可
47     void pop()
48     {
49         if(data.size() > 0)
50         {
51             data.pop_back();
52             minIndex.pop_back();
53         }
54     }
55     
56     //min操作直接返回data里的最小值
57     int min()
58     {
59         return data[minIndex[minIndex.size()-1];
60     }
61 };
62 
63 int main(int argc, char *argv[])
64 {
65     return 0;
66 }