A stack interview question solved with PHP_PHP tutorial

Foreword

I encountered an interview question, and the general meaning of the question is as follows:

Use two ordinary stacks to implement a special stack, so that the pop, push, and min functions are all operations with a complexity of O(1). The min function is to obtain the minimum value of the current stack.

Initial Thoughts

1. To implement the min function as (1) operation, the first idea at that time was to calculate the current minimum value in advance, so I thought of using a value to save the minimum element in the current stack, and then perform push and pop operations. Maintain this value. In this way, min and push are both O(1), but pop is not. If the current pop-up is the minimum value, you need to find the minimum value of the current element again, which is not O(1).

2. And the above method does not use another stack, so I thought of storing the sorted elements in a stack, and also maintaining this ordered stack during push and pop operations, as shown in the figure:

But in this case, the min operation is O(1), but because the push and pop operations need to maintain this ordered stack, I can't think of a method that can achieve O(1) complexity.

At that time, I thought that the minimum value information must be cached in another stack, but I don’t know whether it was because I didn’t eat or something, so my thinking froze.

Correct solution

I felt very unhappy when I couldn't solve a problem, so while eating, I started thinking about how to fully understand the characteristics of the stack and effectively cache the minimum value information for use in min operations.

The biggest feature of stack operation is that it can only operate on the top element of the stack. It is not just right to use an auxiliary stack to cache the minimum value of each stack operation. In this way, every time a pop operation is performed, both sides can be popped together; because the top element of the auxiliary stack is the smallest value in the current stack, the push operation only needs to compare the pushed element and the top element of the auxiliary stack. In this way, push, pop, and min are all O(1) operations. As shown in the picture:

The text may not be clear. Here is the code. Below is the PHP implementation, which simulates the stack through an array.

<&#63;php
/**
 * 使用一个辅助栈，O(1)复杂度求出栈中的最小数
 * @hack 类中通过数组来模拟堆栈
 * 
 * @author laiwenhui
 */
class strack{

  /**
   * 数据栈，存储栈数据；
   *
   * @var array
   */
  private $_arrData = array();
  /**
   * 辅助栈，存储数据组栈中每层的最下值信息；
   *
   * @var array
   */
  private $_arrMin = array();
  /**
   * 栈顶所在单元
   *
   * @var int
   */
  private $_top=-1;
  /**
   * 出栈
   * @return bool|int
   */
  public function pop(){
    if ($this->_top === -1){
      return false;
    }
    array_pop($this->_arrMin);
    $this->_top--;
    return array_pop($this->_arrData);
  }
  /**
   * 入栈
   * @param int $element
   * @return bool
   */
  public function push($element){
    $element = intval($element);
    //如果栈为空，直接入栈
    if ($this->_top === -1){
      array_push($this->_arrData, $element);
      array_push($this->_arrMin, $element);
      $this->_top++;
      return true;
    }
    //不为空，判断入栈的值是否比最小栈栈顶小
    $min = $this->_arrMin[$this->_top];
    //比较求出最小值
    $currentMin = $element < $min &#63; $element : $min;
    //当前栈中最小值入栈
    array_push($this->_arrMin, $currentMin);
    //数据入栈
    array_push($this->_arrData, $element);
    $this->_top++;

    return true;
  }
  /**
   * 求当前栈空间的最小值
   * @return bool|int 
   */
  public function min(){
    if ($this->_top === -1){
      return false;
    }
    return $this->_arrMin[$this->_top];
  }
}

Use as follows:

The output is:

OK, requirements met.

Do you have any other better ways to achieve this? If so, please tell me^_^