Ex30 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

解题思路

维持两个栈：

• stack1提供正常的stack的功能；
• stack2记录一个当前的最小值的栈。

代码

class MinStack
{
public:
  /** initialize your data structure here. */
  MinStack () {}

  void
  push (int x)
  {
    if (stack2_.empty () || stack2_.top () >= x)
      {
        stack2_.push (x);
      }
    else
      {
        stack2_.push (stack2_.top ());
      }
    stack1_.push (x);
  }

  void
  pop ()
  {
    if (!stack1_.empty ())
      {
        stack1_.pop ();
        stack2_.pop ();
      }
  }

  int
  top ()
  {
    return stack1_.top ();
  }

  int
  min ()
  {
    return stack2_.top ();
  }

private:
  std::stack<int> stack1_;
  std::stack<int> stack2_;
};

结果

执行结果：通过

执行用时：40 ms, 在所有 C++ 提交中击败了81.37%的用户

内存消耗：15.2 MB, 在所有 C++ 提交中击败了17.05%的用户