5841. Find the Longest Valid Obstacle Course at Each Position

tag: monotone-stack, greedy, Maximum Increasing Subsequence

Description

Solution

Use monotone-stack to find the longest subsequence end with obstacles[i]

Greedily replace the very obstacles[j], j < i that exactly greater than obstacles[i], other elements in the stack just remain

1 3 5 7 4

stack : 1 3 5 7
after : 1 3 4 7

Just be careful about the same number should also be inclueded, so just binary search for (obstacle[i] + 1)

Code

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        vector<int> dp;
        vector<int> res;
        for(int i = 0; i < obstacles.size(); i++){
            auto pos = lower_bound(dp.begin(), dp.end(), obstacles[i]+1);
            if(pos != dp.end()){
                *pos = obstacles[i];
                res.push_back(pos - dp.begin() + 1);
            }else{
                dp.push_back(obstacles[i]);
                res.push_back(dp.size());
            }
        }
        return res;
    }
};