# LeetCode - 1964. Find the Longest Valid Obstacle Course at Each Position
### 題目網址：https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
###### tags: `LeetCode` `Hard` `貪心演算法（Greedy Algorithm）`

/*
    -LeetCode format-
    Problem: 1964. Find the Longest Valid Obstacle Course at Each Position
    Difficulty: Hard
    
    by Inversionpeter
*/



vector <int> LIS(100000), answers(100000);
vector <int>::iterator toReplace;

static const auto Initialize = [] {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	return nullptr;
}();

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        answers.clear(); LIS = { 0 };
        for (int &height : obstacles)
            if (LIS.back() <= height) {
                answers.push_back(LIS.size());
                LIS.push_back(height);
            }
            else {
                toReplace = upper_bound(LIS.begin(), LIS.end(), height);
                answers.push_back(int(toReplace - LIS.begin()));
                *toReplace = height;
            }
        return answers;
    }
};