## Algorithm

Problem Name: 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the `MinStack` class:

• `MinStack()` initializes the stack object.
• `void push(int val)` pushes the element `val` onto the stack.
• `void pop()` removes the element on the top of the stack.
• `int top()` gets the top element of the stack.
• `int getMin()` retrieves the minimum element in the stack.

You must implement a solution with `O(1)` time complexity for each function.

Example 1:

```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
```

Constraints:

• `-231 <= val <= 231 - 1`
• Methods `pop`, `top` and `getMin` operations will always be called on non-empty stacks.
• At most `3 * 104` calls will be made to `push`, `pop`, `top`, and `getMin`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
class MinStack {
private:
int sz = 1000;
int sp;
int *buff;
int min;
public:
/** initialize your data structure here. */
MinStack() {
buff = (int *)malloc(sz * sizeof(int));
//assert(buff);
sp = 0;
}

void push(int x) {
if (sp == 0 || min > x) min = x;
if (sp == sz) {
sz = sz * 2;
buff = (int *)realloc((void *)buff, sz * sizeof(int));
//assert(buff);
}
buff[sp ++] = x;
}

void pop() {
int i, x = buff[-- sp];
if (min == x) {
for (i = 0; i  <  sp; i ++) {
if (i == 0 || min > buff[i]) min = buff[i];
}
}
}

int top() {
if (sp) return buff[(sp - 1)];
return -1;
}

int getMin() {
return min;
}
};
``````
Copy The Code &

Input

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

Output

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

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class MinStack {
private:
stack<int>s;
stack < int>min;
public:
/** initialize your data structure here. */
MinStack() {}

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

void pop() {
if(s.top() == min.top()) min.pop();
s.pop();
}

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

int getMin() {
return min.top(>;
}
};
``````
Copy The Code &

Input

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

Output

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

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class MinStack {
private final Stack<int[]> stack;

public MinStack() {
this.stack = new Stack < >();
}

public void push(int val) {
int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
stack.push(new int[]{val, min});
}

public void pop() {
stack.pop();
}

public int top() {
return stack.peek()[0];
}

public int getMin() {
return stack.peek()[1];
}
}
``````
Copy The Code &

Input

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

Output

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

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MinStack = function () {
this.stack = []
this.min = null
}

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
if (this.min === null) {
this.min = x
} else {
this.min = Math.min(x, this.min)
}
return this.stack.push(x)
}

/**
* @return {void}
*/
MinStack.prototype.pop = function () {
let removed = this.stack.pop()
if (this.min === removed) {
this.min = this.stack.length > 0 ? Math.min(...this.stack) : null
}
return this.stack
}

/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stack[this.stack.length - 1]
}

/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.min
}
``````
Copy The Code &

Input

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

Output

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

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class MinStack:

def __init__(self):
"""
"""
self.data = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
if not self.data or x < self.data[-1][1]: self.data.append([x, x])
else: self.data.append([x, self.data[-1][1]])
def pop(self):
"""
:rtype: void
"""
self.data.pop()
def top(self):
"""
:rtype: int
"""
return self.data[-1][0]
def getMin(self):
"""
:rtype: int
"""
return self.data[-1][1]
``````
Copy The Code &

Input

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

Output

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

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0155_MinStack
{

/** initialize your data structure here. */
public _0155_MinStack()
{
}

public void Push(int x)
{
else
}

public void Pop()
{
}

public int Top()
{
}

public int GetMin()
{
}

private class Node
{
public Node(int value, int minValue, Node next = null)
{
Value = value;
MinValue = minValue;
Next = next;
}

public int Value { get; set; }
public int MinValue { get; set; }
public Node Next { get; set; }
}

``````
Copy The Code &

Input

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

Output

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