今天的題單：

• Product of Array Except Self

• Min Stack

238. Product of Array Except Self

思路: 分開算 prefix product 和 postfix product 再相乘。

需要記 prefix 和 suffix 兩個 array，時間和空間都是 O(n)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> prefix(nums.size(), 1);
        vector<int> suffix(nums.size(), 1);

        for (int i = 1; i < nums.size(); i++) {
            prefix[i] *= nums[i-1] * prefix[i-1];
        }

        for (int i = nums.size()-2; i >= 0; i--) {
            suffix[i] *= nums[i+1] * suffix[i+1];
        }

        for (int i = 0; i < nums.size(); i++) {
            prefix[i] *= suffix[i];
        }

        return prefix;

    }
};

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

suffix product 可以只需要用一個數字紀錄，在計算 productExceptSelf 結果的 loop 中邊乘邊算，不需要先算完，可以節省一個 array 個空間。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> prefix(nums.size(), 1);
        // vector<int> suffix(nums.size(), 1);
        int suffix = 1;

        for (int i = 1; i < nums.size(); i++) {
            prefix[i] *= nums[i-1] * prefix[i-1];
        }

        for (int i = nums.size()-2; i >= 0; i--) {
            suffix = nums[i+1] * suffix;
            prefix[i] *= suffix;
        }

        return prefix;

    }
};

155. Min Stack

Min Stack 普通的 stack 差別是需要能夠在 O(1) time 得到當前 stack 中最小的 element。因此需要想辦法紀錄 stack 裡的最小值。

思路：stack 裡的每一個 element 都多記一個值：在該 element 以下的 stack 的最小值。
每當有新的 element 要 push 進來的時候比較新的 element 和當前 stack 的 min value，也就是 top element 紀錄的 min value，並把結果紀錄連同 push 進 stack。

class MinStack {
public:
    MinStack() : curr_min(INT_MAX) {
        
    }
    
    void push(int val) {
        if (curr_min > val) {
            this->curr_min = val;
            this->stk.push({val, curr_min});
        } else {
            this->stk.push({val, curr_min});
        }
    }
    
    void pop() {   
        this->stk.pop();
        if (!this->stk.empty()) {
            this->curr_min = this->stk.top().second;
        } else {
            this->curr_min = INT_MAX;
        }
    }
    
    int top() {
        return this->stk.top().first;
    }
    
    int getMin() {
        return this->curr_min;
    }
private:
    int curr_min;
    stack<pair<int, int>> stk;
};

/**
 * 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();
 */