我的LeetCode：https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 155. 最小棧 題目 設計一個支持 push ，pop ，t ...
我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 155. 最小棧
題目
設計一個支持 push ，pop ，top 操作，並能在常數時間內檢索到最小元素的棧。
- push(x) —— 將元素 x 推入棧中。
- pop() —— 刪除棧頂的元素。
- top() —— 獲取棧頂元素。
- getMin() —— 檢索棧中的最小元素。
示例:
輸入：
["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.
提示：
- pop、top 和 getMin 操作總是在 非空棧 上調用。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/min-stack
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
解題思路
本題核心要解決的是如何記錄最小值的問題；
思路1-使用雙棧，其中一個為單調遞減棧，記錄最小值；
步驟：
- 一個棧正常記錄數據，一個棧為單調遞減棧，只記錄比當前棧頂元素小或等於的值（連續相等的值都需要記錄，若只記錄一次，同值出棧後最小值記錄會丟失）；
- 出棧時若為當前最小棧的棧頂值則最小棧也出棧；
演算法複雜度:
- 時間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
- 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
思路2-自己構造節點鏈表
步驟：
- 定義節點，頭節點總記錄當前值以及當前最小值；
- 入棧時更新頭結點和最小值，出棧時直接更新頭結點為其next即可；
演算法複雜度:
- 時間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
- 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
思路3-使用雙數組/list記錄
步驟：
- 定義存儲數據和最小值的數組，註意最小值的初值處理；
- 入棧出棧等價於改變數組的index，註意數組的擴容問題，此處擴容為原數組的1.5倍；
演算法複雜度:
- 時間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
- 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
演算法源碼示例
package leetcode;
import java.util.Arrays;
import java.util.Stack;
/**
* @author ZhouJie
* @date 2020年5月3日 下午4:00:43
* @Description: 155. 最小棧
*
*/
public class LeetCode_0155 {
}
/**
* @author ZhouJie
* @date 2020年5月3日 下午3:23:07
* @Description: 1-兩個棧，一個作輔助棧存單調遞減值；
*
*/
class MinStack_0155_1 {
private Stack<Integer> data;
private Stack<Integer> min;
/** initialize your data structure here. */
public MinStack_0155_1() {
this.data = new Stack<Integer>();
this.min = new Stack<Integer>();
}
public void push(int x) {
data.push(x);
if (min.isEmpty() || x <= min.peek()) {
min.push(x);
}
}
public void pop() {
if (!data.isEmpty()) {
if (min.peek().intValue() == data.pop().intValue()) {
min.pop();
}
}
}
public int top() {
if (data.isEmpty()) {
return -1;
}
return data.peek();
}
public int getMin() {
if (min.isEmpty()) {
return -1;
}
return min.peek();
}
}
/**
* @author ZhouJie
* @date 2020年5月3日 下午3:23:47
* @Description: 2-構造鏈表
*
*/
class MinStack_0155_2 {
private Node head;
/** initialize your data structure here. */
public MinStack_0155_2() {
}
public void push(int x) {
if (head == null) {
head = new Node(x, x, null);
} else {
head = new Node(x, Math.min(x, head.min), head);
}
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
private static class Node {
int val;
int min;
Node next;
public Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
/**
* @author ZhouJie
* @date 2020年5月3日 下午3:45:08
* @Description: 3-使用數組保存數據
*
*/
class MinStack_0155_3 {
private int[] data;
private int[] min;
private int head;
private int cap = 1024;
/** initialize your data structure here. */
public MinStack_0155_3() {
this.head = 0;
this.data = new int[cap];
this.min = new int[cap];
min[0] = Integer.MAX_VALUE;
}
public void push(int x) {
if (head == cap - 2) {
// 擴容至原來的1.5倍
cap = cap + (cap >> 1);
data = Arrays.copyOf(data, cap);
min = Arrays.copyOf(min, cap);
}
data[++head] = x;
min[head] = (head == 1) ? x : Math.min(min[head - 1], x);
}
public void pop() {
if (head > 0) {
head--;
}
}
public int top() {
return head > 0 ? data[head] : -1;
}
public int getMin() {
return head > 0 ? min[head] : -1;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
