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ù)的棧實例的詳細內(nèi)容，更多關于java算法包含min函數(shù)的棧的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要為大家詳細介紹了jetty運行時無法保存文件的解決方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-11-11
java?集合工具類Collections及Comparable和Comparator排序詳解
這篇文章主要介紹了java集合工具類Collections及Comparable和Comparator排序詳解，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-06-06
這篇文章主要介紹了.idea文件夾里面iml文件的作用及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08
這篇文章主要介紹了?Java數(shù)據(jù)結構的十大排序，排序算法分為比較類排序和非比較類排序，具體的內(nèi)容，需要的朋友參考下面思維導圖及文章介紹，希望對你有所幫助2022-01-01
vim是一個高度可配置的文本編輯器,非常穩(wěn)定,可以高效的創(chuàng)建任何文本、持久的、多級撤銷樹、支持數(shù)百種變成語言和格式、與許多工具集成,本文給大家分享了idea使用Vim的技巧大全,需要的朋友可以參考下2024-05-05
java集合類ArrayList和Vector的區(qū)別面試精講
這篇文章主要為大家介紹了java集合類ArrayList和Vector的區(qū)別面試全面講解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-10-10
IDEA遠程連接HBase及其Java API實戰(zhàn)詳解
這篇文章主要介紹了IDEA遠程連接HBase及其Java API實戰(zhàn)詳解,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
這篇文章主要介紹了完美解決request請求流只能讀取一次的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08
這篇文章主要介紹了springboot項目如何引用公共模塊的bean問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08
擴展Hibernate使用自定義數(shù)據(jù)庫連接池的方法
這篇文章主要介紹了擴展Hibernate使用自定義數(shù)據(jù)庫連接池的方法,涉及Hibernate數(shù)據(jù)庫操作擴展的相關技巧,需要的朋友可以參考下2016-03-03