定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃?lèi)型中實(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.

提示

各函數(shù)的調(diào)用總次數(shù)不超過(guò) 20000 次

方法：輔助棧

棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，為了滿(mǎn)足題目的要求，我們建立了一個(gè)輔助棧用于存放最小值，核心思想就是：當(dāng)每入棧一個(gè)值的時(shí)候，同時(shí)輔助棧存入最小值即可。

算法如下：

• MinStack：分別初始化棧、輔助棧、以及存放到輔助棧最大值（用最大值占位，入棧的時(shí)候不需要判空處理）；

• push：兩個(gè)棧存值，注意輔助棧存值需要進(jìn)行比對(duì)最小值；

• pop：兩個(gè)棧出棧

• top：返回棧的頭（新）元素

• min：返回最小值，直接返回輔助棧的頭元素即可

流程圖說(shuō)明：

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：對(duì)于題目中的所有操作，時(shí)間復(fù)雜度均為 O(1)。因?yàn)闂５牟迦?、刪除與讀取操作都是 O(1)，我們定義的每個(gè)操作最多調(diào)用棧操作兩次。

• 空間復(fù)雜度：O(n)，其中 n 為總操作數(shù)。最壞情況下，我們會(huì)連續(xù)插入 n 個(gè)元素，此時(shí)兩個(gè)棧占用的空間為 O(n)。

END

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。