Algorithm
Problem Name: 155. Min Stack
Problem Link:https://leetcode.com/problems/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 elementvalonto 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,topandgetMinoperations will always be called on non-empty stacks. - At most
3 * 104calls will be made topush,pop,top, andgetMin.
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;
}
};
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[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(>;
}
};
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[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];
}
}
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[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
}
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
#5 Code Example with Python Programming
Code -
Python Programming
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
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]
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[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
{
private Node head;
/** initialize your data structure here. */
public _0155_MinStack()
{
head = null;
}
public void Push(int x)
{
if (head == null)
head = new Node(x, x);
else
head = new Node(x, Math.Min(x, head.MinValue), head);
}
public void Pop()
{
head = head.Next;
}
public int Top()
{
return head.Value;
}
public int GetMin()
{
return head.MinValue;
}
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; }
}
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]