定义栈的数据结构，要求添加一个min的函数，能够得到栈的最下元素。
要求函数min, push, pop的时间复杂度都是O(1)
1 class stackmin {
2 int data[N];
3 int minidx[N];
4 int top;
5 public:
6 stackmin()
7 : top(-1)
8 {
9 ::memset(minidx, -1, sizeof(int)*N);
10 ::memset(data, 0, sizeof(int)*N);
11 }
12
13 bool push(int d)
14 {
15 if (top < N-1)
16 data[++top] = d;
17 else
18 return false;
19 if (top==0)
20 minidx[top] = 0;
21 else if (data[minidx[top-1]] > d)
22 minidx[top] = top;
23 else
24 minidx[top] = minidx[top-1];
25 return true;
26 }
27 bool pop(int& d)
28 {
29 if (top<0)
30 return false;
31 else
32
33 d = data[top];
34 minidx[top] = -1;
35 top--;
36 return true;
37 }
38 bool min(int& m)
39 {
40 if (top>=0)
41 m = data[minidx[top]];
42 else
43 return false;
44 return true;
45 }
46 void print()
47 {
48 for (int i = 0; i <= top; i++)
49 std::cout << data[i] << " ";
50 std::cout << "\n";
51 }
52 };
53
借助另一个内部的数组，用来存储每次push元素之后的栈最小值的索引，便可很方便的在O(1)的时间内完成以上三种操作。一种空间换时间的方法。