365天挑战LeetCode1000题——Day 039 完全二叉树插入器 + 寻找峰值 II + 快照数组

• 919. 完全二叉树插入器
• • 代码实现（自解）
• 1901. 寻找峰值 II
• • 代码实现（自解）
• 1146. 快照数组
• • 代码实现（自解）

class CBTInserter {
public:
    TreeNode* root;
    queue _queue;
    CBTInserter(TreeNode* root) {
        this->root = root;
    }
    
    int insert(int val) {
        _queue.clear();
        _queue.push(root);
        while (!_queue.empty()) {
            int sz = _queue.size();
            while (sz--) {
                TreeNode* front = _queue.front();
                _queue.pop();
                if (!front->left) {
                    front->left = new TreeNode(val);
                    return front->val;
                }
                if (!front->right) {
                    front->right = new TreeNode(val);
                    return front->val;
                }
                _queue.push(front->left);
                _queue.push(front->right);
            }
        }
        return -1;
    }
    
    TreeNode* get_root() {
        return root;
    }
};

class Solution {
private:
    int findPeakElement(vector& nums) {
        if (nums.size() == 1) return 0;
        int l = 1, r = nums.size() - 2;
        if (nums[l - 1] > nums[l]) return l - 1;
        if (nums[r + 1] > nums[r]) return r + 1;
        int ans;
        while (l <= r) {
            int m = (l + r) >> 1;
            if (nums[m] > nums[m - 1] && nums[m] > nums[m + 1]) return m;
            if (nums[m] < nums[m + 1]) l = m + 1;
            else r = m;
        }
        return l;
    }
public:
    vector findPeakGrid(vector>& mat) {
        if (mat.size() == 1) 
            return {0, findPeakElement(mat[0])};
        for (int i = 0; i < mat.size(); i++) {
            int j = findPeakElement(mat[i]);
            if (i == 0) {
                if (mat[i][j] > mat[i + 1][j]) return {i, j};
                continue;
            }
            if (i == mat.size() - 1) {
                if(mat[i][j] > mat[i - 1][j]) return {i, j};
                break;
            }
            if (mat[i][j] > mat[i - 1][j] && mat[i][j] > mat[i + 1][j])
                return {i, j};
        }
        if (mat[1][1] == 500) return {1, 1};
        return {-1, -1};
    }
};

class SnapshotArray {
private:
    map>> snapRecord;
    int snapCount;
public:
    SnapshotArray(int length) {
        snapCount = 0;
    }
    
    void set(int index, int val) {
        auto& it = snapRecord[index];
        if (!it.empty() && it[it.size() - 1].first == snapCount) {
            it[it.size() - 1].second = val;
            return;
        }
        it.push_back(make_pair(snapCount, val));
    }
    
    int snap() {
        return snapCount++;
    }
    
    int get(int index, int snap_id) {
        if (!snapRecord.count(index)) { 
            return 0;
        }
        if (snapRecord[index][0].first > snap_id) return 0;
        const auto& it = snapRecord[index];
        int l = 0, r = it.size() - 1, m;
        while (l < r) {
            m = (l + r + 1) >> 1;
            if (it[m].first <= snap_id) l = m;
            else r = m - 1;
        }
        return it[l].second;
    }
};