#155. Min Stack

題目描述

設計一個具有push、pop、top以及能夠在常數時間內取得最小值功能的Stack。

實作MinStack類別：

• MinStack() 初始化物件.
• void push(int val) 將元素val放入Stack。
• void pop() 移除最上方的元素。
• int top() 回傳最上方的元素。
• int getMin() 取得最小值的元素。
• 每個方法的時間複雜度都必須是O(1)。

限制條件

1. -2³¹ <= val <= 2³¹ - 1
2. pop、top、getMin只會在有元素的情況下被呼叫。
3. 最多只會呼叫3 * 104次由push、pop、top、getMin組成的函式。

解題思路

這一題比較需要思考的是如何實作getMin這個方法，其實也很簡單，就是將Stack儲存的型別使用Tuple來儲存就可以了。

Tuple由兩個數值組成，第一個是存入的數值，第二個則是當前的最小值。

基本上Stack可以儲存任何資料結構，所以只要有能儲存上述兩個數值的資料結構就可以解決最小值的問題。

Solution

public class MinStack {
    private Stack<(int,int)> _st;    
    public MinStack() {
        _st = new Stack<(int,int)>();
    }
    
    public void Push(int val) {
        if(_st.Count==0){ 
            _st.Push((val,val));
        }else {
            (int v,int prev_min) = _st.Peek();
            _st.Push((val,Math.Min(prev_min,val)));
        } 
    }
    
    public void Pop() {
        _st.Pop();        
    }
    
    public int Top() {
        (int v,int min) = _st.Peek();
        return v;
    }
    
    public int GetMin() {
        (int v,int min) = _st.Peek();
        return min;
    }
}

複雜度分析：

• 時間複雜度：每個函式都是O(1)。
• 空間複雜度：每個函式都是O(1)，整個類別是O(n)。

學習重點

• Design