##設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的堆疊， push(x) -- 將元素 x 推入堆疊中， pop() -- 洗掉堆疊頂的元素， top() -- 獲取堆疊頂元素， getMin() -- 檢索堆疊中的最小元素，
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 回傳 -3.
minStack.pop();
minStack.top(); --> 回傳 0.
minStack.getMin(); --> 回傳 -2.
思路
以空間換時間，采用輔助堆疊，
輔助堆疊可以分為同步輔助堆疊和不同步輔助堆疊兩種，
同步輔助堆疊：
額外設定一個堆疊，同步保存當前資料堆疊的最小值，該輔助堆疊所push的值遞減（非嚴格遞減），pop與push操作與資料堆疊同步，
getMin時間復雜度O(1)，空間復雜度O(n)，
不同步輔助堆疊：
額外設定一個堆疊，保存當前資料堆疊的最小值，同樣也是遞減堆疊，pop與push操作與資料堆疊不同步：
僅當 資料堆疊push操作的資料 ＜＝ 輔助堆疊的堆疊頂值（最小值），輔助堆疊才進行push更新，
僅當 資料堆疊pop操作的資料 == 輔助堆疊的堆疊頂值（最小值），輔助堆疊才進行pop更新，
getMin時間復雜度O(1)，空間復雜度O(n)，
代碼
- 同步輔助堆疊
import java.util.*;
class MinStack {
private Stack<Integer> data;
private Stack<Integer> helper;
/** initialize your data structure here. */
public MinStack() {
data = https://www.cnblogs.com/ustca/p/new Stack();
helper = new Stack();
}
public void push(int x) {
data.push(x);
if(helper.isEmpty() || x - 不同步輔助堆疊
import java.util.*;
class MinStack {
private Stack<Integer> data;
private Stack<Integer> helper;
/** initialize your data structure here. */
public MinStack() {
data = https://www.cnblogs.com/ustca/p/new Stack();
helper = new Stack();
}
public void push(int x) {
data.push(x);
if(helper.isEmpty() || x<=helper.peek()) {
helper.push(x);
}
}
public void pop() {
if(!data.isEmpty()) {
if(data.peek().equals(helper.peek())) {
helper.pop();
}
data.pop();
}
}
public int top() {
if(!data.isEmpty()) {
return data.peek();
}
throw new RuntimeException("堆疊空，堆疊頂無元素");
}
public int getMin() {
if(!data.isEmpty()) {
return helper.get(helper.size()-1);
}
throw new RuntimeException("堆疊空，堆疊無最小值");
}
}
筆記
-
輔助堆疊使用ArrayList代替Stack難以看到優勢，反而降低編碼效率；
ArrayList擴容因子為1.5，Stack擴容因子為2；
Java集合框架圖：
-
data.peek().equals(helper.peek())
包裝型別為參考型別，不能直接等于號比較，
Integer包裝類僅在比較的整數值在-128 - 127時可以比較，
Integer相關原始碼：
public static Integer valueOf(int i) {
if (i >= IntegerCache.low && i <= IntegerCache.high)
return IntegerCache.cache[i + (-IntegerCache.low)];
return new Integer(i);
}
private static class IntegerCache {
static final int low = -128;
static final int high;
static final Integer cache[];
static {
// high value may be configured by property
int h = 127;
String integerCacheHighPropValue =
https://www.cnblogs.com/ustca/p/sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
if (integerCacheHighPropValue != null) {
try {
int i = parseInt(integerCacheHighPropValue);
i = Math.max(i, 127);
// Maximum array size is Integer.MAX_VALUE
h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
} catch( NumberFormatException nfe) {
// If the property cannot be parsed into an int, ignore it.
}
}
high = h;
cache = new Integer[(high - low) + 1];
int j = low;
for(int k = 0; k < cache.length; k++)
cache[k] = new Integer(j++);
// range [-128, 127] must be interned (JLS7 5.1.7)
assert IntegerCache.high >= 127;
}
private IntegerCache() {}
}
當數值在-128 - 127時，靜態內部類IntegerCache使用同一cache陣列共享資料，
鏈接：https://leetcode-cn.com/problems/min-stack
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91939.html
標籤：其他
上一篇：什么是資料結構？