定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min的函數(shù)，能夠得到棧的最下元素。
要求函數(shù)min, push, pop的時(shí)間復(fù)雜度都是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
借助另一個(gè)內(nèi)部的數(shù)組，用來存儲每次push元素之后的棧最小值的索引，便可很方便的在O(1)的時(shí)間內(nèi)完成以上三種操作。一種空間換時(shí)間的方法。