Leetcode-简单-第155题

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

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

其中前面3个函数还是非常的简单，可以用常规的数组就可以实现。 主要思考的是第4个函数getMin() —— 检索栈中的最小元素。 如果不考虑任何的时间复杂度和空间复杂度，我们可以直接通过最常用的方式，找出数组中最小的元素返回。但是算法要求能在常数时间内检索到最小元素的栈，也就是时间复杂度是O(1)。

解题思路

我们先复习下栈的特性

  • 先进后出
  • 对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出

解题方法我们可以采用双栈方式，一个栈存储正常元素，一个栈存储最小元素。 参考如下：

class MinStack {
    
    var stackList:[Int]
    var minStackList:[Int]

     /** initialize your data structure here. */
     init() {
        stackList = []
        minStackList = []
     }
     
     func push(_ x: Int) {
        stackList.append(x)
        if let lastMin = minStackList.last{
            minStackList.append(min(x, lastMin))
        }else{
            minStackList.append(x)
        }
     }
     
     func pop() {
         stackList.removeLast()
        minStackList.removeLast()
     }
     
     func top() -> Int {
        return stackList.last!
     }
     
     func getMin() -> Int {
        return minStackList.last!
     }
 }