設計一個保護 min 函數的棧，min 函數返回棧的最小元素。并且 min、push、pop 函數的時間復雜度都為 O(1)。
主要思想是定義一個輔助棧記錄最小元素在原棧中的索引。
實現中參考：
http://hi.baidu.com/xiangzifengshi/blog/item/2f9e833aef17d6f7828b131e.htmlhttp://zhedahht.blog.163.com/blog/static/25411174200712895228171/代碼實現：
1 #include <iostream>
2 #include <ctime>
3 #include <cassert>
4 using namespace std;
5
6 class MinStack
7 {
8 private:
9 int stack[100];
10 int p;
11 int minstack[100];
12 int q;
13
14 bool minEmpty()
15 {
16 return q == 0;
17 }
18 void minPop()
19 {
20 assert(!minEmpty());
21 --q;
22 }
23 int minTop()
24 {
25 assert(!minEmpty());
26 return minstack[q - 1];
27 }
28 public:
29 MinStack() : p(0), q(0) {}
30 bool empty()
31 {
32 return p == 0;
33 }
34 void push(int i)
35 {
36 stack[p++] = i;
37 if (minEmpty())
38 {
39 minstack[q++] = p - 1;
40 }
41 else
42 {
43 if (i <= stack[minTop()])
44 {
45 minstack[q++] = p - 1;
46 }
47 }
48 }
49 void pop()
50 {
51 assert(!empty());
52 if (top() == stack[minTop()])
53 {
54 minPop();
55 }
56 --p;
57 }
58 int min()
59 {
60 assert(!empty());
61 return stack[minTop()];
62 }
63 int top()
64 {
65 assert(!empty());
66 return stack[p - 1];
67 }
68 };
69
70 int main()
71 {
72 MinStack ms;
73 srand(time(0));
74 for (int i = 0; i < 10; ++i)
75 {
76 int n = rand() % 100;
77 ms.push(n);
78 }
79 while (!ms.empty())
80 {
81 cout << ms.top() << '\t' << ms.min() << endl;
82 ms.pop();
83 }
84 return 0;
85 }
posted on 2011-04-23 01:28
unixfy 閱讀(162)
評論(0) 編輯 收藏 引用