Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.
Solution:
the StackMin class which keeps the top Element and the current MinElement and implements the three functions: push, pop and min:
class MinStack { class Node{ int val; int min; } Stack<Node> st = new Stack<Node>(); public void push(int x) { Node node = new Node(); node.val = x; if(st.isEmpty()){ node.min=x; }else{ Node top = st.peek(); if(top.min <x){ node.min=top.min; }else{ node.min=x; } } st.push(node); } public void pop() { st.pop(); } public int top() { return st.peek().val; } public int getMin() { return st.peek().min; } }
Dear Sir/Madam,
I found this article useful. n I am really grateful to u for that. but I wanted to ask u “can i publish this info on my blog”. so that my friends will get some help too.