LeetCode - 155 解題紀錄

題目： LeetCode - 155. Min Stack

題目說明

設計一個 Stack，並完成部分功能。

解題思路

可以直接使用 STL 的容器，所以只須明白 Stack 的運作模式即可。

• 解法一
  Vector：速度較慢。( 因為插入與刪除元素的代價較高 )

• 解法二
  Stack：速度較快，這邊使用 stack<pair<int, int>> 來增加取得最小值的效率。

參考解法

解法一：

class MinStack {
public:
    /** initialize your data structure here. */
    vector<int> minstack;
    
    MinStack() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
    }
    
    void push(int x) {
        minstack.push_back(x);
    }
    
    void pop() {
        minstack.pop_back();
    }
    
    int top() {
        return minstack.back();
    }
    
    int getMin() {
        return *(min_element(minstack.begin(), minstack.end()));
    }
};

解法二：

class MinStack {
public:
    /** initialize your data structure here. */
    stack<pair<int, int>> minstack;
    
    MinStack() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
    }
    
    void push(int x) {
        if(minstack.empty() || minstack.top().second >= x)
            minstack.push({x, x});
        else
            minstack.push({x, minstack.top().second});
    }
    
    void pop() {
        minstack.pop();
    }
    
    int top() {
        return minstack.top().first;
    }
    
    int getMin() {
        return minstack.top().second;
    }
};

2020-08-18 重寫

// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        if(s.empty()) { s.emplace(x, x); return; }
        s.emplace(x, x < s.top().second ? x : s.top().second);
    }
    
    void pop() { s.pop(); }
    
    int top() { return s.top().first; }
    
    int getMin() { return s.top().second; }
private:
    stack<pair<int, int>> s;
};