LeetCode: Min Stack Solution

Approach

Use an linked list to store stack

Head node will be top of the stack and will store the minimum of the stack

Every push will recalculate the minimum

Implementation

1function Node(val, min, next) {
2  this.val = val
3  this.min = min
4  this.next = next
5}
6
7var MinStack = function () {
8  this.head = null
9}
10
11MinStack.prototype.push = function (val) {
12  this.head = new Node(
13    val,
14    this.head ? Math.min(val, this.head.min) : val,
15    this.head
16  )
17}
18
19MinStack.prototype.pop = function () {
20  this.head = this.head.next
21}
22
23MinStack.prototype.top = function () {
24  return this.head.val
25}
26
27MinStack.prototype.getMin = function () {
28  return this.head.min
29}

References

Original problem

Similar problems

Sliding Window Maximum

Max Stack