題目描述
定義棧的資料結構，請在該類型中實作一個能夠得到棧最小元素的min函數。要求時間複雜度是o(1)。
還是先說一下思路吧，因為每次方元素進棧的時候不能保證棧頂元素都是最小的，是以需要想辦法使得棧頂元素始終是最小的元素，排序是一種思路，但是每次排序還設計重新出棧和入棧，想來應該不是這樣的。一種思路是可以利用一個輔助棧，相當于是以空間換時間了。具體思路是：當入棧的新元素原先棧頂元素小的話就該元素放入一個輔助棧中，如果新入棧的元素比原先棧頂元素大，則在輔助棧中繼續放原先最小的元素。這樣一直放下去，當需要取最小元素的時候，就從輔助棧中取棧頂元素即可，這樣的話時間複雜度就是o(1)了。而且這麼做還有一個好處，就是去了最小元素後，下一次取的時次小的元素（仍然是最小的）。基于這種思路，寫出如下代碼（已被牛客ac）：