要求
定义栈的数据结构,要求添加一个min 函数,能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。
解法1:
使用一个辅助栈来保存最小元素,这个解法简单不失优雅。设该辅助栈名字为minimum stack,其栈顶元素为当前栈中的最小元素。这意味着
- 要获取当前栈中最小元素,只需要返回minimum stack的栈顶元素即可。
- 每次执行push操作,检查push的元素是否小于或等于minimum stack栈顶元素。如果是,则也push该元素到minimum stack中。
- 当执行pop操作的时候,检查pop的元素是否与当前最小值相等。如果相同,则需要将改元素从minimum stack中pop出去。
struct minStack{ stack<int> s; stack<int> minS; void push(int i){ if (s.empty() || minS.empty()){ s.push(i); minS.push(i); }else{ if (minS.top() >= i){ minS.push(i); } s.push(i); } } void pop(){ if (s.empty() || minS.empty()){ return; } if (s.top() > minS.top()){ s.pop(); }else{ s.pop(); minS.pop(); } } int min(){ if (minS.empty()) return -1; else return minS.top(); } };
2.巧妙解法
另外一种解法利用存储差值而不需要辅助栈,方法比较巧妙。其中需要说明的几点:
push(int elem)函数在栈中压入当前元素与当前栈中最小元素的差值,然后通过比较当前元素与当前栈中最小元素大小,并将它们中间的较小值压入。
pop()函数执行的时候,先pop出栈顶的两个值,这两个值分别是当前栈中最小值min和最后压入的元素与栈中最小值的差值diff。如果diff<0,则表示最后压入栈的元素是最小的元素,因此只需将min-diff压入栈中,并将min值返回即可。min-diff就是当前元素弹出后,栈中剩下元素的最小值。而如果diff>=0且栈不为空,则表示当前值不是最小值,所以需要在栈中压入最小值min并将diff+min返回;如果栈为空,则表示已经是最后一个数字,直接返回min即可。
struct minStackLessSpace{ void push(int i){ if (s.empty()){ s.push(i); s.push(i); } if (i - s.top() < 0){ s.pop(); s.push(i-s.top()); s.push(i); }else{ int j = s.top(); s.pop(); s.push(i); s.push(j); } } bool pop(){ if (s.empty()) return false; int i = s.top(); s.pop(); if (s.top() < 0){ int j = s.top(); s.pop(); s.push(i - j); }else{ s.pop(); s.push(i); } } stack<int> s; };
参考:
http://blog.csdn.net/ssjhust123/article/details/7752878