【Leetcode】:Min Stack

タイトルリンク:https://oj.leetcode.com/problems/min-stack/
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.

解析:テーマはスタックを設計して定数時間内にpush,pop,topを実行し,最小値minの操作を得ることを要求する.
アルゴリズム1:1つのドメイン値がxであり、もう1つのドメイン値がスタック内の最小値である構造体を確立する.従って、スタック全体の最小値をO(1)時間で得ることができる.しかし、このアルゴリズムの結果は、Memory limit exceed.
アルゴリズム2:s 1の現在のすべての要素の最小値である別のスタックs 2を確立する.
アルゴリズムのコード:

#include<iostream>
#include<stack>

using namespace std;

class MinStack
{
private:
        typedef struct Node
        {
            int val;
            int min_temp;        
        }tNode; 
        stack<tNode> s;
        
public: 
       void push(int x)    
       {
           tNode n;
           n.val = x;
           if( s.empty() )
           {
               n.min_temp = x;
           }
           else
           {
               if( x < s.top().min_temp )    
               {
                   n.min_temp = x;     
               }
               else
               {
                   n.min_temp = s.top().min_temp;    
               }
           }
           s.push(n);
       }
       void pop()
       {
           s.pop();     
       }
       int top()
       {
           return s.top().val;    
       }
       int getMin()
       {
           return s.top().min_temp;    
       }
};

int main()
{
	MinStack ms;
	ms.push(1);
	ms.push(2);
	ms.push(3);
	ms.push(4);
	ms.push(5);

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();
	
	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

    system("pause");
	return 0;
}<strong>
</strong>

結果は:memory limit exceed.その原因はmin_tempドメインは、各要素が最小値を保存するので、必要ありません.
アルゴリズム2のAC+完全コード:

#include<iostream>
#include<stack>

using namespace std;

class MinStack
{
private:
	stack<int> s1;
	stack<int> s2;
public:
	void push(int x)
	{
		s1.push(x);
		if( s2.empty() )
		{
			s2.push(x);
		}
		else if( x <= s2.top() )
		{
			s2.push(x);
		}
	}

	void pop()
	{
		int top = s1.top();
		s1.pop();
		if( top<=s2.top() )
		{
			s2.pop();
		}
	}
	int top()
	{
		return s1.top();	
	}
	int getMin()
	{
		return s2.top();
	}
};

int main()
{
	MinStack ms;
	ms.push(1);
	ms.push(2);
	ms.push(3);
	ms.push(4);
	ms.push(5);

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();
	
	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

	cout<<"top = "<<ms.top()<<" min = "<<ms.getMin()<<endl;
	ms.pop();

    system("pause");
	return 0;
}