https://leetcode.com/problems/min-stack/

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

두개의 stack을 가지고 풀었다. 과감하게 space complexity 를 n만큼 손해보더라도!

하나의 stack에는 원래대로 쌓이게 두면 된다.

다른 stack은 들어오는 수가 이 stack의 top()의 값보다 작을 때만 넣어주거나 같으면 pair의 second를 count개념으로두고 ++ 해준다.

따라서 중복되는 수는 계속 쌓이는것이 아닌pair로 관리되어서 조금이라도 space를 아낄수 있다.

class MinStack {
public:
	/** initialize your data structure here. */
	std::stack<int> normalStack;
	std::stack<pair<int, int>> minStack;
	int minNum = INT_MAX;
	MinStack() {
	}

	void push(int x) {
		normalStack.push(x);
		if (minStack.empty())
		{
			minStack.push(make_pair(x, 1));
		}
		else
		{
			if (minStack.top().first > x)  // 더 작은 값이 들어올 때만 넣어주면 된다.
			{
				minStack.push(make_pair(x, 1));
			}
			else if (minStack.top().first == x)
			{
				minStack.top().second++;
			}
		}
	}

	void pop() {
		if (normalStack.empty()) return;
		if (minStack.top().first == normalStack.top())
		{
			minStack.top().second--;
			if (minStack.top().second == 0)
				minStack.pop();
		}
		normalStack.pop();

	}

	int top() {
		if (normalStack.empty()) return NULL;
		return normalStack.top();
	}

	int getMin() {
		if (minStack.empty()) return NULL;
		return minStack.top().first;
	}
};

이는 어디까지나 optimization의 관점이므로, space complexity 는 O(n)이다.

time complexity는 O(1)으로 해결된다.