題目

定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時(shí)間復(fù)雜度都是 O(1)。

示例

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

Swift

//包含min函數(shù)的棧
class MinStack {
    var listStack:[Int] = [Int]()
    var minListStack:[Int] = [Int]()
    /** initialize your data structure here. */
    init() {

    }
    
    func push(_ x: Int) {
        listStack.append(x)
        if let currentMinValue = minListStack.last {
            if x < currentMinValue {
                minListStack.append(x)
            } else {
                minListStack.append(currentMinValue)
            }
        } else {
            minListStack.append(x)
        }
    }
    
    func pop() {
        if listStack.isEmpty == false && minListStack.isEmpty == false {
            listStack.removeLast()
            minListStack.removeLast()
        } else {
           //異常處理(兩個(gè)數(shù)組個(gè)數(shù)不相等的情況處理)
            if listStack.isEmpty == false {
                listStack.removeAll()
            }
            if minListStack.isEmpty == false {
                minListStack.removeAll()
            }
        }
    }
    
    func top() -> Int {
        if let tempTop = listStack.last {
            return tempTop
        }
        return -1;
    }
    
    func min() -> Int {
        if let tempTop = minListStack.last {
            return tempTop
        }
        return -1;
    }
}

var minStack = MinStack()
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();
minStack.pop();
minStack.top();
minStack.min();

Java

待更新