初级算法-设计问题-最小栈

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

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

摘一个示例做个说明.
示例 1：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

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

条件分析:

1. 栈设计,就是所谓的压入栈,弹出栈操作
2. 最小元素获取 -> 需要快速获取最小值

解决思路1:

1. 根据分析1,采用数据结构数组进行操作
2. 设计最小值

利用数组的特性进行压入、弹出操作,设计最小值属性,直接返回

class MinStack {
    /// 栈数据存储
    var data: [Int] = []
    /// 最小值
    var minNum: Int?

    init() {
    }
    
    func push(_ val: Int) {
        /// 入栈,数组加操作,然后对比最小值
        self.data.append(val)
        minNum = min(minNum ?? .max, val)
    }
    
    func pop() {
        /// 出栈
        let last = self.data.popLast()
        /// 最小值判断
        if last == minNum {
            minNum = self.data.min()
        }
    }
    
    func top() -> Int {
        return self.data.last!
    }
    
    func getMin() -> Int {
        return minNum!
    }
}

最小栈提交结果.jpg

测试用例:

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

考察要点:

• 栈
• 设计