155.Min-Stack.md

155. Min Stack

Problem

---

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.

Note

---

• Use to Stack
  • one stack for storing value
  • one stack for storing minimum value in this moment

Code

---

• PHP

  Runtime 21ms Beats 95.45% of users with PHP

  Memory 23.86MB Beats 51.14% of users with PHP

  class MinStack {
      private array $stack;
      private array $minStack;
      private int $count;
  
      /**
       */
      function __construct(
      ) {
          $this->stack = [];
          $this->minStack = [];
          $this->count = 0;
      }
    
      /**
       * @param Integer $val
       * @return NULL
       */
      function push($val) {
          $this->stack[] = $val;
          if ($this->count == 0 || $this->minStack[$this->count - 1] > $val) {
              $this->minStack[] = $val;
          } else {
              $this->minStack[] = $this->minStack[$this->count - 1];
          }
  
          $this->count++;
      }
    
      /**
       * @return NULL
       */
      function pop() {
          array_pop($this->stack);
          array_pop($this->minStack);
          $this->count--;
      }
    
      /**
       * @return Integer
       */
      function top() {
          return $this->stack[$this->count - 1];
      }
    
      /**
       * @return Integer
       */
      function getMin() {
          return $this->minStack[$this->count - 1];
      }
  }
  
  /**
   * Your MinStack object will be instantiated and called as such:
   * $obj = MinStack();
   * $obj->push($val);
   * $obj->pop();
   * $ret_3 = $obj->top();
   * $ret_4 = $obj->getMin();
   */

• GoLang

  Runtime 12ms Beats 79.03% of users with Go

  Memory 7.63 MB Beats 11.31% of users with Go

  type MinStack struct {
      stack *linkedliststack.Stack
      minStack *linkedliststack.Stack
  }
  
  func Constructor() MinStack {
      return MinStack{stack: linkedliststack.New(), minStack: linkedliststack.New()}
  }
  
  func (this *MinStack) Push(val int)  {
      this.stack.Push(val)
      min, _ := this.minStack.Peek()
      if this.minStack.Empty() || min.(int) > val {
          this.minStack.Push(val)
      } else {
          this.minStack.Push(min.(int))
      }
  }
  
  func (this *MinStack) Pop()  {
      this.stack.Pop()
      this.minStack.Pop()
  }
  
  func (this *MinStack) Top() int {
      top, _ := this.stack.Peek()
      return top.(int)
  }
  
  func (this *MinStack) GetMin() int {
      min, _ := this.minStack.Peek()
      return min.(int)
  }
  
  /**
   * Your MinStack object will be instantiated and called as such:
   * obj := Constructor();
   * obj.Push(val);
   * obj.Pop();
   * param_3 := obj.Top();
   * param_4 := obj.GetMin();
   */

Reference

---

• https://www.youtube.com/watch?v=qkLl7nAwDPo&ab_channel=NeetCode