LeetCode:一番小さいスタックの実現

push,pop,top動作をサポートするよう設計し,定数時間内に最小要素のスタックを検索できる.
push(x)–元素xをスタックに押し込む.pop()–スタックトップの要素を削除します.top()–スタックトップ要素を取得します.get Min()–スタックの最小要素を検索します.
例:MinStock minStock=new MinStock()minStock.push(-2)minStock.push(0)minStock.push(-3)minStock.getMin()－>は-3.minStock.pop()を返します.minStock.top()>>は、0を返します.minStock.getMin();>は-2を返します
ソース:スナップリンク:https://leetcode-cn.com/problems/min-stack 分析:1つのスタックで最小要素を検索し、定数時間内では遍歴してはいけません.私たちは変数または配列を用いてスタックの中の最小要素を保存しようと試みましたが、具体的には、一番小さいスタックを構築し、最初の要素を同時に一番小さいスタックに入れます.このようにして、最も小さいスタックのスタックトップ要素は常にスタック中の最小要素である.コードの実装:

#include
#include
using namespace std;
class MinStack
{
	stack<int> m_st;
	stack<int> min_st;
public:
	/** initialize your data structure here. */
	MinStack()
	{

	}

	void push(int x)
	{
		m_st.push(x);
		if (min_st.size() == 0||min_st.top() >= x)
		{
			min_st.push(x);
		}
	}

	void pop()
	{
		int tmp = m_st.top();
		m_st.pop();
		if (min_st.top() == tmp)
		{
			min_st.pop();
		}
	}

	int top()
	{
		return m_st.top();
	}

	int getMin()
	{
		return min_st.top();
	}
};

int main()
{
	MinStack minStack;
	minStack.push(-3);
	minStack.push(-2);
	minStack.push(0);
	minStack.push(-3);
	cout << minStack.getMin() << endl;
	minStack.pop();
	cout << minStack.top() << endl;
	cout << minStack.getMin() << endl;

	return 0;
}

上は主にpopとpushの中でmin_を保証することを実現します.stスタックのトップは常にm_であるstの最小要素また、スペースの複雑さはO(1)の最適化です.ここをクリックして、オーディエンスの文章を学ぶことができます.