首页 > 代码库 > Min Stack (10)

Min Stack (10)

2024-08-01 10:00:16   217人阅读

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.

题目意思很简单，即建立一个stack，除了最基本的push pop top 三大函数之外，这个堆栈还能够返回堆栈中的最小值。整个题目完成以后，我有两种解题思路，并付诸实现了。

第一种解题思路是自定义stack 结点，在结点中定义一个指针用来储存存入这个元素之后stack中最小元素的位置。代码如下，很失望的是，leetcode显示内存超限。看来这种方法不行啊。先把代码贴出来吧。

 1 class node{ 2 public: 3     int value; 4     node *ptr,*next; 5     node(int value=http://www.mamicode.com/0){ 6         this->value=http://www.mamicode.com/value; 7         ptr=next=NULL; 8     } 9 };10 class stack{11 private:12     node *min;13     node *head;14 public:15     stack(){16         head=NULL;17         min=NULL;18     }19     void pop(){20         if(!head)21             return;22         node *link=head;23         head=head->next;24         delete link;25     }26     27     void push(int x){28         node *link=head;29         node *temp=new node(x);30         if(!head){31             min=temp;32         }33         else{34             if(x<=min->value){35                 min=temp;36             }37         }38         temp->ptr=min;39         temp->next=head;40         head=temp;41     }42     node *top(){43         return head;44     }45     int m(){46         if(!head)47             return -1;48         return head->ptr->value;49     }50 51 };

另外一种方法是用两个stack s,t，s用来储存真实的数据，t专门用来存储最小的数据。这里的最小的定义是当前size的stack中最小的数据。当执行pop指令时，如果pop出的数据等于最小数据时才将t弹出一个。当压入数据的时候，只有要压入的数据小于t栈顶的数据时才将其压入t，否则只压入s.这样的话节省了一部份空间，不用对s中每一个位置的元素都在t中存储该位置对应的最小元素。ps:不按这种做法，会显示内存超出限制。

先贴出内存超限的代码:

 1 class MinStack { 2 public: 3     stack<int>s; 4     stack<int>t; 5     void push(int x) { 6         s.push(x); 7         if(t.empty()){ 8             t.push(x); 9         }10         else{11             int temp=t.top();12             if(x<temp)13                 t.push(x);14             else15                 t.push(temp);16         }17     }18 19     void pop() {20         t.pop();21         s.pop();22     }23 24     int top() {25         return s.top();26     }27 28     int getMin() {29       30       int temp= t.top();31       return temp;32     }33 };

相应的，节省空间的代码是：

 1 class MinStack { 2 public: 3     void push(int x) { 4         s.push(x); 5         if (t.empty() || t.top()>= x) t.push(x);//注意这里不能取>  否则如果有两个连续的最小值输入的话，若果弹出其中一个的话，返回的最小值可能会出错。 6     } 7  8     void pop() { 9         int top = s.top(); s.pop();10         if (top == t.top()) t.pop();11     }12 13     int top() {14         return s.top();15     }16 17     int getMin() {18         return t.top();19     }20 private:21     stack<int> s;22     stack<int> t;23 };

 

Min Stack (10)


联系
我们