LeetCode（算法）- 155. 最小栈

题目链接：点击打开链接

题目大意：略。

解题思路：略。

相关企业

字节跳动亚马逊（Amazon）Facebook微软（Microsoft）彭博（Bloomberg）VMware谷歌（Google）Shopee

AC 代码

Java

// 解决方案(1)
class MinStack {
 
    private final int[] data;
 
    private final int[] minData;
 
    private int p;
 
    private int minP;
 
    
    public MinStack() {
        data = new int[20000];
        minData = new int[20000];
        p = -1;
        minP = -1;
    }
 
    public void push(int x) {
        data[++p] = x;
        if (-1 == minP || minData[minP] >= x) {
            minData[++minP] = x;
        }
    }
    
    public void pop() {
        int cur = top();
        data[p--] = 0;
        if (cur == minData[minP]) {
            minData[minP--] = 0;
        }
    }
    
    public int top() {
        return data[p];
    }
    
    public int getMin() {
        return minData[minP];
    }
}
 
// 解决方案(2)
class MinStack {
    Stack A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int getMin() {
        return B.peek();
    }
}
 

C++

class MinStack {
public:
    stack A, B;
    MinStack() {}
    void push(int x) {
        A.push(x);
        if(B.empty() || B.top() >= x)
            B.push(x);
    }
    void pop() {
        if(A.top() == B.top())
            B.pop();
        A.pop();
    }
    int top() {
        return A.top();
    }
    int getMin() {
        return B.top();
    }
};