問題描述

定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O(1)）。

解題思路

筆試時，能通過為大。如果能使用 Java 庫中的數據數據和方法就盡量使用。

思路：對 Stack 的原有方法進行封裝，數據存入棧 data之中，并借助一個輔助棧 min 來存放最小值。

入棧時，data 棧正常入棧；然后將 node 與 min棧的棧頂元素比較大小，如果 min 棧頂為空或者 node 較小就入輔助棧 min ，否則不如 min 棧。

出棧時，min 的棧頂元素若與棧data 的棧頂元素一樣，則棧min 也需要出棧；否則棧min 不執行出棧。

Java 代碼

import java.util.Stack;public class Solution {private Stack<Integer> data = new Stack<>();private Stack<Integer> min = new Stack<>();public void push(int node) {data.push(node);if (min.isEmpty() || node < min.peek()) {min.push(node);}}public void pop() {if (data.peek() == min.peek()) {data.pop();min.pop();} else {data.pop();}}public int top() {return data.peek();}public int min() {return min.peek();} }

復雜度分析：

• 時間復雜度：O(1) --> 因為直接使用了棧的數據結構，出棧入棧的時間復雜度為 O(1)

總結

以上是生活随笔為你收集整理的剑指Offer：包含main函数的栈(借助辅助栈)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。