java算法題解LeetCode30包含min函數(shù)的棧實(shí)例
題目
劍指 Offer 30. 包含min函數(shù)的棧 定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?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 次
解題思路
1.題目要求實(shí)現(xiàn)的最小返回其實(shí)不難，最簡(jiǎn)單的，只需要去排序就可以了，但是這樣的話，無(wú)法保證調(diào)用 min、push 及 pop 的時(shí)間復(fù)雜度都是 O(1)
2.正常一個(gè)棧的push、pop、peek的時(shí)間復(fù)雜度都是 O(1)，那么現(xiàn)在就是想辦法去解決，min函數(shù)時(shí)間復(fù)雜度的問(wèn)題了？
3.既然題目限制了時(shí)間復(fù)雜度，那么這時(shí)我們可以想一下，是否可以借助空間來(lái)實(shí)現(xiàn)？使用輔助棧？
4.一個(gè)棧是主棧 stackstack，另一個(gè)是輔助棧 minStackminStack，用于存放對(duì)應(yīng)主棧不同時(shí)期的最小值
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ù)的棧實(shí)例的詳細(xì)內(nèi)容，更多關(guān)于java算法包含min函數(shù)的棧的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
- Java C++題解leetcode1620網(wǎng)絡(luò)信號(hào)最好的坐標(biāo)
- Java?C++刷題leetcode1106解析布爾表達(dá)式
- Java C++題解leetcode816模糊坐標(biāo)示例
- Java C++題解leetcode 1684統(tǒng)計(jì)一致字符串的數(shù)目示例
- Java?C++題解leetcode764最大加號(hào)標(biāo)志示例
- java算法題解Leetcode763劃分字母區(qū)間示例
- java算法題解LeetCode35復(fù)雜鏈表的復(fù)制實(shí)例
- java?LeetCode刷題稍有難度的貪心構(gòu)造算法
相關(guān)文章
今天小編就為大家分享一篇關(guān)于Spring的Bean容器介紹，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-01-01
這篇文章主要介紹了java對(duì)象轉(zhuǎn)型的概念及用法,并以實(shí)例形式進(jìn)行了較為詳細(xì)的介紹,需要的朋友可以參考下2014-10-10
Spring Boot整合Spring Cache及Redis過(guò)程解析
這篇文章主要介紹了Spring Boot整合Spring Cache及Redis過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12
配置IDEA中java項(xiàng)目配置swagger全過(guò)程
這篇文章主要介紹了配置IDEA中java項(xiàng)目配置swagger全過(guò)程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-05-05
emoji表情與unicode編碼互轉(zhuǎn)的實(shí)現(xiàn)(JS,JAVA,C#)
這篇文章主要介紹了emoji表情與unicode編碼互轉(zhuǎn)的實(shí)現(xiàn)(JS,JAVA,C#)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
微服務(wù)通過(guò)Feign調(diào)用進(jìn)行密碼安全認(rèn)證操作
這篇文章主要介紹了微服務(wù)通過(guò)Feign調(diào)用進(jìn)行密碼安全認(rèn)證操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06
mybatis 如何判斷l(xiāng)ist集合是否包含指定數(shù)據(jù)
這篇文章主要介紹了mybatis 判斷l(xiāng)ist集合是否包含指定數(shù)據(jù)的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06
本文將利用Java語(yǔ)言實(shí)現(xiàn)浪漫流星表白，可以實(shí)現(xiàn)這些功能：播放音樂(lè)、自定義流星數(shù)量、飛行速度、光暈大小、流星大小，自定義表白話語(yǔ)，感興趣的可以學(xué)習(xí)一下2022-05-05
本篇文章主要介紹了詳解springmvc 參數(shù)綁定，詳細(xì)的介紹了springmvc各種參數(shù)綁定的情況，具有一定的參考價(jià)值，有興趣的可以了解一下。2017-03-03
這篇文章主要介紹了Mybatis批量插入和批量更新失敗問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-08-08