劍指offer 包含min函式的棧

2022-11-24 15:01:42 字數 718 閱讀 2149

定義棧的資料結構,請在該型別中實現一個能夠得到棧中所含最小元素的min函式(時間複雜度應為o(1))。

思路:我們可以用一個變數儲存當前棧最小元素,但是當棧頂元素為最小元素,且被彈出時,變數應該儲存次小元素,所以只用一個變數是不行的。也就是說,在我們儲存最小元素之前,應該把次小元素儲存起來。

我們可以用輔助棧儲存最小元素,每次新壓入一個元素到棧中,比較輔助棧的棧頂元素(當前棧的最小元素),如果新壓入的元素不大於棧頂元素(考慮了壓入棧的元素值可能重複),則壓入輔助棧,作為當前棧的最小元素。

當彈出棧的元素時,如果彈出元素和輔助棧棧頂元素相同,說明應彈出輔助棧頂元素。

步驟操作

資料棧輔助棧

最小值1

壓入3333

2壓入4

3,4333

壓入23,4,2

3,22

4壓入1

3,4,2,1

3,2,115

彈出3,4,2

3,22

6壓入2

3,4,2,2

3,2,227

彈出3,4,2

3,228彈出

3,43

3

1

class

solution

11void

pop()

18int

top()

24int

min()

30 };

劍指offer(20)包含min函式的棧

定義棧的資料結構,請在該型別中實現一個能夠得到棧最小元素的min函式。首先一開始我們分析得到最小值肯定要比較嘛,和棧裡面的資料一一比較,但是棧這種資料結構,你又只能和棧頂彈出來的資料進行比較,所以肯定需要一個臨時棧嘛,當然這只是一種思路,就是其餘的操作pop,push這些和棧的操作一樣,只是min的...

劍指 Offer 30 包含min函式的棧

這裡參考 面試題30.包含 min 函式的棧 輔助棧,清晰 相似題目 劍指 offer 59 i.滑動視窗的最大值 1 class minstack 1011 void push int x 21 22 23void pop 2829 inttop 3233 intgetmin 36 3738 39...

劍指offer包含min函式的棧python

定義棧的資料結構,請在該型別中實現一個能夠得到棧中所含最小元素的min函式 時間複雜度應為o 1 定義兩個棧,一個儲存正常的資料,另一個用來記錄當前的最小元素 coding utf 8 class solution def init self self.stack1 self.stack2 self...