leetcode：155. 最小栈

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例：

  1. 输入：
  2. ["MinStack","push","push","push","getMin","pop","top","getMin"]
  3. [[],[-2],[0],[-3],[],[],[],[]]
  5. 输出：
  6. [null,null,null,null,-3,null,0,-2]
  8. 解释：
  9. MinStack minStack = new MinStack();
  10. minStack.push(-2);
  11. minStack.push(0);
  12. minStack.push(-3);
  13. minStack.getMin();   --> 返回 -3.
  14. minStack.pop();
  15. minStack.top();      --> 返回 0.
  16. minStack.getMin();   --> 返回 -2.

解答 & 代码

  1. class MinStack {
  2. private:
  3.     stack<int> dataS;    // 数据栈
  4.     stack<int> minS;    // 最小值栈，栈顶元素值代表当前数据栈中的最小元素值
  5. public:
  6.     MinStack() {
  7.     }
  9.     void push(int val) {
  10.         dataS.push(val);
  11.         if(minS.empty() || minS.top() > val)
  12.             minS.push(val);
  13.         else
  14.             minS.push(minS.top());
  15.     }
  17.     void pop() {
  18.         if(!dataS.empty())
  19.             dataS.pop();
  20.         if(!minS.empty())
  21.             minS.pop();
  22.     }
  24.     int top() {
  25.         return dataS.empty() ? -1 : dataS.top();
  26.     }
  28.     int getMin() {
  29.         return minS.empty() ? -1 : minS.top();
  30.     }
  31. };
  33. /**
  34.  * Your MinStack object will be instantiated and called as such:
  35.  * MinStack* obj = new MinStack();
  36.  * obj->push(val);
  37.  * obj->pop();
  38.  * int param_3 = obj->top();
  39.  * int param_4 = obj->getMin();
  40.  */

复杂度分析：总操作数 N

  • 时间复杂度：每个操作的时间复杂度均为 O(1)
  • 空间复杂度 O(N)：若 N 个操作都为插入，则栈的空间复杂度 O(N)

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 72.20% 的用户
  4. 内存消耗：16 MB, 在所有 C++ 提交中击败了 33.78% 的用户