首页 > 其他 > 详细

LeetCode - Min Stack

时间:2015-01-23 13:19:24      阅读:251      评论:0      收藏:0      [点我收藏+]

Min Stack

2015.1.23 12:13

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  push(x) -- Push element x onto stack.

  pop() -- Removes the element on top of the stack.

  top() -- Get the top element.

  getMin() -- Retrieve the minimum element in the stack.

Solution:

  This could almost be counted as a FAQ. You‘ll find a same question in "Cracking the Coding Interview". A min stack is maintained alongside the data stack, recording every minimal (so far) element. The min stack is updated whever a new minimal value is being pushed, or the current minimal value is being popped.

  Total time complexity for each operation is strictly O(1). Extra space of O(n) is required to maintain the min stack.

Accepted code:

 1 // 1AC, old
 2 #include <stack>
 3 using namespace std;
 4 
 5 class MinStack {
 6 public:
 7     void push(int x) {
 8         if (ms.empty() || ms.top() >= x) {
 9             ms.push(x);
10         }
11         s.push(x);
12     }
13 
14     void pop() {
15         if (s.top() == ms.top()) {
16             ms.pop();
17         }
18         s.pop();
19     }
20 
21     int top() {
22         return s.top();
23     }
24 
25     int getMin() {
26         return ms.top();
27     }
28 private:
29     stack<int> s, ms;
30 };

 

LeetCode - Min Stack

原文:http://www.cnblogs.com/zhuli19901106/p/4243876.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!