911. 在线选举

911. 在线选举

times是严格递增的，所以只需要预处理记录每个时间段谁的票多，就可以得出每个时间点的获胜者，在搜索的时候，找到不大于t的最大时间点的胜者即可

class TopVotedCandidate {
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
        unordered_map<int, int> memo;
        int top = -1;
        int maxVote = -1;
        for(auto p : persons)
        {
            if(++memo[p] >= maxVote)
            {
                top = p;
                maxVote = memo[p];
            }
            tops.push_back(top);
        }
    }
    
    int q(int t) {
        // 寻找第一个大于t的时间点
        auto pos = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return tops[pos];
    }
private:
    vector<int> tops;
    vector<int> times;
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */