Sponsored
Sponsored
In this approach, we use a combination of dynamic programming and binary search to find the longest obstacle course at each position. We maintain a list which helps to track the longest increasing subsequence (LIS) up to the current index. For each obstacle, we find its position in the LIS using binary search (which keeps it sorted), updating the LIS while also determining the length of the LIS at each step.
Time Complexity: O(n log n), as each binary search operation runs in O(log n) and is performed n times. Space Complexity: O(n), storing the longest sequence lengths.
1import java.util.*;
2
3public class LongestObstacleCourse {
4 public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
5 int n = obstacles.length;
6 List<Integer> lis = new ArrayList<>();
7 int[] ans = new int[n];
8 for (int i = 0; i < n; i++) {
9 int obstacle = obstacles[i];
10 int pos = Collections.binarySearch(lis, obstacle);
11 if (pos < 0) pos = -(pos + 1);
12 ans[i] = pos + 1;
13 if (pos == lis.size()) {
14 lis.add(obstacle);
15 } else {
16 lis.set(pos, obstacle);
17 }
18 }
19 return ans;
20 }
21}
22The Java solution manages a list to keep track of the increasing sequence. Collections.binarySearch() helps to find the right position and modifies the current list as necessary.
This approach uses a Fenwick Tree (or BIT) to keep track of the lengths of obstacle courses efficiently. As we iterate through the obstacles array, we update our Fenwick Tree with the longest course length ending at each obstacle using range queries.
Time Complexity: O(n log m), where m is the maximum obstacle height. Space Complexity: O(m).
1#include <vector>
2#include <algorithm>
3
4class FenwickTree {
5 std::vector<int> tree;
int size;
public:
FenwickTree(int size) : size(size), tree(size + 1, 0) {}
void update(int index, int value) {
for (; index <= size; index += index & -index)
tree[index] = std::max(tree[index], value);
}
int query(int index) const {
int max_val = 0;
for (; index > 0; index -= index & -index)
max_val = std::max(max_val, tree[index]);
return max_val;
}
};
std::vector<int> longestObstacleCourseAtEachPosition(const std::vector<int>& obstacles) {
int max_obstacle = *max_element(obstacles.begin(), obstacles.end());
FenwickTree fenwick(max_obstacle);
std::vector<int> result;
for (auto obs : obstacles) {
int cur_len = fenwick.query(obs) + 1;
result.push_back(cur_len);
fenwick.update(obs, cur_len);
}
return result;
}The C++ version leverages a Fenwick Tree class designed to handle maximum queries and updates efficiently, focused on maintaining the longest course lengths during iteration.