Leetcode 分類刷題 —— 棧（Stack）

1、題目描述：

Leetcode 155. Min Stack (follow up Leetcode 716 Max Stack 最小棧)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
實(shí)現(xiàn) MinStack 類:
MinStack() 初始化堆棧對(duì)象。
void push(int val) 將元素val推入堆棧。
void pop() 刪除堆棧頂部的元素。
int top() 獲取堆棧頂部的元素。
int getMin() 獲取堆棧中的最小元素。

2、解題思路：

使用兩個(gè)棧，一個(gè)用于存儲(chǔ)元素，另一個(gè)用于存儲(chǔ)當(dāng)前的最小值。
在插入元素時(shí)，將元素入棧，并將當(dāng)前最小值與元素比較。如果最小值棧為空或者當(dāng)前元素小于等于最小值棧頂元素，則將當(dāng)前元素也入最小值棧。
在彈出元素時(shí)，如果棧頂元素等于最小值棧頂元素，則將最小值棧頂元素也出棧。
由于每個(gè)元素最多被入棧和出棧各一次，因此時(shí)間復(fù)雜度是O(1)，空間復(fù)雜度是O(n)。

3、代碼

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack; // 用來存儲(chǔ)元素
    private Stack<Integer> minStack; // 用來存儲(chǔ)當(dāng)前最小值

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val); // 將元素入棧
        if (minStack.isEmpty() || val <= minStack.peek()) {
            // 如果最小值棧為空或者當(dāng)前元素小于等于最小值棧頂元素，則將當(dāng)前元素也入最小值棧
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop(); // 將棧頂元素出棧
        if (val == minStack.peek()) {
            // 如果棧頂元素等于最小值棧頂元素，則將最小值棧頂元素也出棧
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek(); // 返回棧頂元素
    }

    public int getMin() {
        return minStack.peek(); // 返回最小值棧頂元素
    }
}