[Swift]LeetCode155. 最小栈 | Min Stack_app

概述Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get t

Design a stack that supports push,pop,top,and retrIEving the minimum element in constant time.

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- RetrIEve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> Returns -3.minStack.pop();minStack.top();      --> Returns 0.minStack.getMin();   --> Returns -2.

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

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

示例:

MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> 返回 -3.minStack.pop();minStack.top();      --> 返回 0.minStack.getMin();   --> 返回 -2.

136ms

 1 class MinStack { 2      3     var stack: [Int] 4     var minStack: [Int] 5      6     /** initialize your data structure here. */ 7     init() { 8         stack = [] 9         minStack = []10     }11     12     func push(_ x: Int) {13         stack.append(x)14         if minStack.count == 0 {15             minStack.append(x)16         } else {17             minStack.append(min(x,minStack[minStack.count - 1]))18         }19     }20     21     func pop() {22         stack.removeLast()23         minStack.removeLast()24     }25     26     func top() -> Int {27         return stack[stack.count - 1]28     }29     30     func getMin() -> Int {31         return minStack[minStack.count - 1]32     }33 }34 35 36 /**37  * Your MinStack object will be instantiated and called as such:38  * let obj = MinStack()39  * obj.push(x)40  * obj.pop()41  * let ret_3: Int = obj.top()42  * let ret_4: Int = obj.getMin()43  */44

140ms

 1 class MinStack { 2  3     /** initialize your data structure here. */ 4     var stackArray: [Int] 5     var minIndex: Int = 0 6     init() { 7       stackArray = [Int]() 8     } 9     10     func push(_ x: Int) {11       stackArray.append(x)12       let currMin = stackArray[minIndex]13       if x < currMin {14           minIndex = stackArray.count - 115       }16     }17     18     func pop() {19       stackArray.removeLast()20       adjustMinIndex()21     }22     23     func top() -> Int {24       return stackArray.last ?? 025     }26     27     func getMin() -> Int {28       return stackArray[minIndex]29     }30 31     func adjustMinIndex() {32         minIndex = 033         guard stackArray.count > 1 else {return}34         var temp = stackArray[minIndex]35         for i in 1..<stackArray.count {36           if stackArray[i] < temp {37             temp = stackArray[i]38             minIndex = i39           }40         }41     }42 }

144ms

 1 class MinStack { 2     //需要使用双栈实现 3     //保存数据 4     var stack: [Int] 5     //保存最小值 6     var sm: [Int] 7     /** initialize your data structure here. */ 8     init() { 9         stack = [Int]()10         sm = [Int]()11     }12     13     func push(_ x: Int) {14         stack.append(x)15         if sm.isEmpty || (!sm.isEmpty && sm.last! >= x)16         {17             sm.append(x)18         }19     }20     21     func pop() {22         if stack.last! == sm.last!23         {24             sm.removeLast()25         }26         stack.removeLast()27     }28     29     func top() -> Int {30         //获取堆栈第一个元素31         return stack.last!32     }33     34     func getMin() -> Int {35         //获取堆栈第一个元素36         return sm.last!37     }38 }39 40 /**41  * Your MinStack object will be instantiated and called as such:42  * let obj = MinStack()43  * obj.push(x)44  * obj.pop()45  * let ret_3: Int = obj.top()46  * let ret_4: Int = obj.getMin()47  */48

144ms

 1 class MinStack { 2  3     private var elements: [(val: Int,minUntil: Int)] 4     /** initialize your data structure here. */ 5     init() { 6         elements = [(val: Int,minUntil: Int)]() 7     } 8      9     func push(_ x: Int) {10         if let lastElement = elements.last {11             elements.append((val: x,minUntil: min(lastElement.minUntil,x)))12         } else {13             elements.append((val: x,minUntil: x))14         }15     }16     17     func pop() {18         elements.removeLast()19     }20     21     func top() -> Int {22       return elements.last!.val23     }24     25     func getMin() -> Int {26       return elements.last!.minUntil27     }28 }29 30 /**31  * Your MinStack object will be instantiated and called as such:32  * let obj = MinStack()33  * obj.push(x)34  * obj.pop()35  * let ret_3: Int = obj.top()36  * let ret_4: Int = obj.getMin()37  */38

152ms

 1 class MinStack { 2  3     private var stack: [(Int,Int)] 4  5     init() { 6         stack = [] 7     } 8  9     func push(_ x: Int) {10         if stack.isEmpty {11             stack.append((x,x))12         } else {13             let top = stack.last!14             stack.append((x,x < top.1 ? x : top.1))15         }16     }17 18     func pop() {19         stack.popLast()20     }21 22     func top() -> Int {23         return stack.last!.024     }25 26     func getMin() -> Int {27         return stack.last!.128     }29 }