定義堆疊的資料結構，請在該型別中實作一個能夠得到堆疊中所含最小元素的 min 函式，時間復雜度應為 O(1)
自定義符合題意的資料結構，當然要考慮使用的現有資料結構來構造，可以使用兩個堆疊來實作題目的要求，
堆疊一用來正常存放資料，堆疊二則負責記錄最小值，每次有新資料入堆疊時，先和堆疊二的最頂層元素比較，如果小于最頂層元素，堆疊一堆疊二同時壓入新值；否則堆疊一壓入新值，堆疊二壓入當前其頂層元素的值，
每次出堆疊時，堆疊一堆疊二同時將資料出堆疊，堆疊一是正常存放資料的，自然不用多說；堆疊二的最頂層資料一定是最小的，每次出堆疊也同時彈出堆疊頂元素，
import java.util.Stack;
public class Solution {
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
if(stack2.empty()) {
stack2.push(node);
}
if(node <= stack2.peek()) {
stack2.push(node);
} else {
stack2.push(stack2.peek());
}
}
public void pop() {
stack1.pop();
stack2.pop();
}
public int top() {
return stack1.peek();
}
public int min() {
return stack2.peek();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/161533.html
標籤：其他