Share my clean AC C++ solution, with explanation.

• The key idea is use a another stack to store the minimum value of the corresponding stack. Put differently, min[i] equals the minimum element where data[i] is the top of this sub-stack.

We can use a full size of min where its size equals the data's, but it's not necessary.

Idea

• We should pop the element in min IFF there's match of data.top().

• If we have multiple same minima, for example [0, 1, 0] in data, then the min should be [0, 0].
Otherwise, the the pop operation wouldn't work properly, since that you need 2 0s.
As a result, we should push the element if x <= min.top().

Code

class MinStack {

stack<int> data;
stack<int> min;

public:

void push(int x) {

// If empty
if (min.empty()) {
data.push(x);
min.push(x);
}

// Not empty
else {
data.push(x);
if (x <= min.top())
min.push(x);
}

}

void pop() {

if (!min.empty()) {
if (data.top() == min.top())
min.pop();
data.pop();
}
}

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

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

• Good explanation and method!! I always got a MLE...

• Here is the situation that your code seems wrong, why it could pass the test?:

Here are the arrays that should be pushed into the data stack: {7,8,4,3,5,6}

Then your min stack will have the elements from bottom to top: {7,4,3}

Then do four times pop(), and then do the getMin(), your answer should be 4. However, it is not in the stack data.

• Nothing's wrong with his/her solution. After doing pop() four times, data stack is {7,8} and min stack will be {7}. getMin() returns 7, which is right.

• push() could be simplified.

void push(int x) {
data.push(x);
if(min.empty() || x <= min.top())
min.push(x);
}

• Instead of a stack of integers, use a stack of pairs where the first key is the value, the second is the min value on the stack:

stack<pair<int, int>>

• Thank you for your comment. In my opinion, using 2 stacks will reduce the usage of space. For example, say a stack with N elements, and the minimum is the first element pushed onto the stack. Then your method will have to push N duplicates of the minimum, which is not necessary here. You don't need to store the minimum every time since it's not updated.

• Thank you for your comment. However after 4 times of pop, the stack should be [7, 8]. Because before the 4th pop, the current top of the stack and the min stack are both 4, which should all be poped.

• Can you please tell me when you titled "clean AC C++ solution", what does "AC" stands for?

• I think AC is the abbreviation of ACCEPTED. It weird at the beginning though.

• Thanks for code.

In my opinion,....the question ask for implement a "STACK"...but not really use a "STL stack".
It won't be accept in interview though...just saying.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.