[Swift]LeetCode155.最小栈|MinStack

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10060297.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新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 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 - 1
15       }
16     }
17     
18     func pop() {
19       stackArray.removeLast()
20       adjustMinIndex()
21     }
22     
23     func top() -> Int {
24       return stackArray.last ?? 0
25     }
26     
27     func getMin() -> Int {
28       return stackArray[minIndex]
29     }
30 
31     func adjustMinIndex() {
32         minIndex = 0
33         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 = i
39           }
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!.val
23     }
24     
25     func getMin() -> Int {
26       return elements.last!.minUntil
27     }
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!.0
24     }
25 
26     func getMin() -> Int {
27         return stack.last!.1
28     }
29 }