一、題目大意
標簽: 堆疊和佇列
https://leetcode.cn/problems/min-stack
設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的堆疊，
實作 MinStack 類:
MinStack() // 初始化堆疊物件，
void push(int val) // 將元素val推入堆疊，
void pop() // 洗掉堆疊頂部的元素，
int top() // 獲取堆疊頂部的元素，
int getMin() // 獲取堆疊中的最小元素，
示例 1:
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]輸出：
[null,null,null,null,-3,null,0,-2]解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 回傳 -3.
minStack.pop();
minStack.top(); --> 回傳 0.
minStack.getMin(); --> 回傳 -2.
提示：
- -231 <= val <= 231 - 1
- pop、top 和 getMin 操作總是在 非空堆疊 上呼叫
- push, pop, top, and getMin最多被呼叫 3 * 104 次
二、解題思路
可以額外建立一個堆疊（最小值堆疊），堆疊頂表示原堆疊中最小值，插入一個數字時，如果該值小于新堆疊的堆疊頂值說明該數是最小值，將其同時插入原堆疊和最小值堆疊，取數時，如果原堆疊的值等于最小值堆疊的值，說明這個數是原堆疊中的最小值，原堆疊和最小值堆疊需要同時移除該元素，
實作：每次插入堆疊時，都向最小值堆疊插入一個原堆疊里所有值的最小值，
三、解題方法
3.1 Java實作
class MinStack {
Stack<Integer> s;
/**
* 輔助堆疊
*/
Stack<Integer> minS;
public MinStack() {
s = new Stack<>();
minS = new Stack<>();
}
public void push(int val) {
s.push(val);
// 注意這里是>=
if (minS.isEmpty() || minS.peek() >= val) {
minS.push(val);
}
}
public void pop() {
int val = s.pop();
if (!minS.isEmpty() && minS.peek() == val) {
minS.pop();
}
}
public int top() {
return s.peek();
}
public int getMin() {
return minS.isEmpty() ? 0 : minS.peek();
}
}
// Integer 與 int 比較
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
四、總結小記
- 2022/8/8 這兩天有大到暴雨，能涼快一些吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501251.html
標籤：其他