劍指offer/LintCode12_最小棧

Betta 發(fā)布于2019-08-14 18:12 / 3101人閱讀

摘要：劍指最小棧聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處解題思路實現(xiàn)功能實現(xiàn)一個最小棧，要求操作均為復雜度，解題思路用棧存儲數(shù)據(jù)用最小棧存儲中最小元素，保證棧頂元素與棧頂元素同步，表示此時最小值將與此時最小值比較，將更小的一方壓棧，保證中棧頂始終

劍指offer/LintCode12_最小棧 聲明

文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處https://segmentfault.com/u/yzwall

解題思路 實現(xiàn)功能：

實現(xiàn)一個最小棧，要求push(element),pop(),min()操作均為$O(1)$復雜度，

解題思路

用棧stack存儲數(shù)據(jù)；

用最小棧minStack存儲stack中最小元素，保證minStack棧頂元素與stack棧頂元素同步，minStack.peek()表示此時stack最小值

push(number)：minStack將number與此時最小值minStack.peek()比較，將更小的一方壓棧，保證minStack中棧頂始終為最小值；

pop()：對stack進行pop()時，同時進行minStack.pop()，保證minStack與stack同步；

注意點

實現(xiàn)最大棧時，

push(number)操作只需push(Math.max(number, minStack.peek())，保證maxStack棧頂元素始終為最大值

pop操作時，maxStack與stack同時pop，保證同步；

題目鏈接

lintcode 12: http://www.lintcode.com/en/problem/min-stack/

Java代碼

/**
 * 實現(xiàn)一個最小棧，要求push,pop,min操作均為O(1)復雜度
 * http://www.lintcode.com/en/problem/min-stack/
 * @author yzwall
 */
import java.util.ArrayDeque;

class MinStack {
    private ArrayDeque stack;
    private ArrayDeque minStack;
    
    MinStack() {
        this.stack = new ArrayDeque<>();
        this.minStack = new ArrayDeque<>();
    }
    
    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            // 實現(xiàn)最大棧時，只需push(Math.max(number, minStack.peek())
            minStack.push(Math.min(number, minStack.peek()));
        }
    }
    
    public int pop() {
        minStack.pop();
        return stack.pop();
    }
    
    public int min() {
        return minStack.peek();
    }
}