java算法題解LeetCode30包含min函數(shù)的棧實例
題目
劍指 Offer 30. 包含min函數(shù)的棧 定義棧的數(shù)據(jù)結構,請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中,調用 min、push 及 pop 的時間復雜度都是 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ù)的調用總次數(shù)不超過 20000 次
解題思路
1.題目要求實現(xiàn)的最小返回其實不難,最簡單的,只需要去排序就可以了,但是這樣的話,無法保證調用 min、push 及 pop 的時間復雜度都是 O(1)
2.正常一個棧的push、pop、peek的時間復雜度都是 O(1),那么現(xiàn)在就是想辦法去解決,min函數(shù)時間復雜度的問題了?
3.既然題目限制了時間復雜度,那么這時我們可以想一下,是否可以借助空間來實現(xiàn)?使用輔助棧?
4.一個棧是主棧 stackstack,另一個是輔助棧 minStackminStack,用于存放對應主棧不同時期的最小值
import java.util.Stack; class MinStack { Stack<Integer> stack; Stack<Integer> minstack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<Integer>(); minstack = new Stack<Integer>(); } public void push(int x) { stack.push(x); if (minstack.isEmpty()) { minstack.push(x); } else { int k = minstack.peek(); if (k > x) { minstack.push(x); } else { minstack.push(k); } } } public void pop() { stack.pop(); minstack.pop(); } public int top() { return stack.peek(); } public int min() { return minstack.peek(); } } /** * Your MinStack object will be instantiated and called as such: MinStack obj = * new MinStack(); obj.push(x); obj.pop(); int param_3 = obj.top(); int param_4 * = obj.min(); */
以上就是java算法題解LeetCode30包含min函數(shù)的棧實例的詳細內容,更多關于java算法包含min函數(shù)的棧的資料請關注腳本之家其它相關文章!
相關文章
Spring Boot整合Spring Cache及Redis過程解析
這篇文章主要介紹了Spring Boot整合Spring Cache及Redis過程解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-12-12emoji表情與unicode編碼互轉的實現(xiàn)(JS,JAVA,C#)
這篇文章主要介紹了emoji表情與unicode編碼互轉的實現(xiàn)(JS,JAVA,C#),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-01-01mybatis 如何判斷l(xiāng)ist集合是否包含指定數(shù)據(jù)
這篇文章主要介紹了mybatis 判斷l(xiāng)ist集合是否包含指定數(shù)據(jù)的操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-06-06