| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
1933 |
第 253 场周赛 Q4 |
|
你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。
对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：
- 你可以选择下标介于
0到i之间（包含0和i）的任意个障碍。 - 在这条路线中，必须包含第
i个障碍。 - 你必须按障碍在
obstacles中的 出现顺序 布置这些障碍。 - 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。
返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。
示例 1：
输入：obstacles = [1,2,3,2] 输出：[1,2,3,3] 解释：每个位置的最长有效障碍路线是： - i = 0: [1], [1] 长度为 1 - i = 1: [1,2], [1,2] 长度为 2 - i = 2: [1,2,3], [1,2,3] 长度为 3 - i = 3: [1,2,3,2], [1,2,2] 长度为 3
示例 2：
输入：obstacles = [2,2,1] 输出：[1,2,1] 解释：每个位置的最长有效障碍路线是： - i = 0: [2], [2] 长度为 1 - i = 1: [2,2], [2,2] 长度为 2 - i = 2: [2,2,1], [1] 长度为 1
示例 3：
输入：obstacles = [3,1,5,6,4,2] 输出：[1,1,2,3,2,2] 解释：每个位置的最长有效障碍路线是： - i = 0: [3], [3] 长度为 1 - i = 1: [3,1], [1] 长度为 1 - i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线 - i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线 - i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线 - i = 5: [3,1,5,6,4,2], [1,2] 长度为 2
提示：
n == obstacles.length1 <= n <= 1051 <= obstacles[i] <= 107
我们可以用树状数组维护一个最长递增子序列的长度数组。
然后对于每个障碍，我们在树状数组中查询小于等于当前障碍的最长递增子序列的长度，假设为
时间复杂度
class BinaryIndexedTree:
__slots__ = ["n", "c"]
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s = max(s, self.c[x])
x -= x & -x
return s
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
nums = sorted(set(obstacles))
n = len(nums)
tree = BinaryIndexedTree(n)
ans = []
for x in obstacles:
i = bisect_left(nums, x) + 1
ans.append(tree.query(i) + 1)
tree.update(i, ans[-1])
return ansclass BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int v) {
while (x <= n) {
c[x] = Math.max(c[x], v);
x += x & -x;
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s = Math.max(s, c[x]);
x -= x & -x;
}
return s;
}
}
class Solution {
public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
int[] nums = obstacles.clone();
Arrays.sort(nums);
int n = nums.length;
int[] ans = new int[n];
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int k = 0; k < n; ++k) {
int x = obstacles[k];
int i = Arrays.binarySearch(nums, x) + 1;
ans[k] = tree.query(i) + 1;
tree.update(i, ans[k]);
}
return ans;
}
}class BinaryIndexedTree {
private:
int n;
vector<int> c;
public:
BinaryIndexedTree(int n) {
this->n = n;
c = vector<int>(n + 1);
}
void update(int x, int v) {
while (x <= n) {
c[x] = max(c[x], v);
x += x & -x;
}
}
int query(int x) {
int s = 0;
while (x > 0) {
s = max(s, c[x]);
x -= x & -x;
}
return s;
}
};
class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> nums = obstacles;
sort(nums.begin(), nums.end());
int n = nums.size();
vector<int> ans(n);
BinaryIndexedTree tree(n);
for (int k = 0; k < n; ++k) {
int x = obstacles[k];
auto it = lower_bound(nums.begin(), nums.end(), x);
int i = distance(nums.begin(), it) + 1;
ans[k] = tree.query(i) + 1;
tree.update(i, ans[k]);
}
return ans;
}
};type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{n, make([]int, n+1)}
}
func (bit *BinaryIndexedTree) update(x, v int) {
for x <= bit.n {
bit.c[x] = max(bit.c[x], v)
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) (s int) {
for x > 0 {
s = max(s, bit.c[x])
x -= x & -x
}
return
}
func longestObstacleCourseAtEachPosition(obstacles []int) (ans []int) {
nums := slices.Clone(obstacles)
sort.Ints(nums)
n := len(nums)
tree := NewBinaryIndexedTree(n)
for k, x := range obstacles {
i := sort.SearchInts(nums, x) + 1
ans = append(ans, tree.query(i)+1)
tree.update(i, ans[k])
}
return
}class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] = Math.max(this.c[x], v);
x += x & -x;
}
}
query(x: number): number {
let s = 0;
while (x > 0) {
s = Math.max(s, this.c[x]);
x -= x & -x;
}
return s;
}
}
function longestObstacleCourseAtEachPosition(obstacles: number[]): number[] {
const nums: number[] = [...obstacles];
nums.sort((a, b) => a - b);
const n: number = nums.length;
const ans: number[] = [];
const tree: BinaryIndexedTree = new BinaryIndexedTree(n);
const search = (x: number): number => {
let [l, r] = [0, n];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let k = 0; k < n; ++k) {
const i: number = search(obstacles[k]) + 1;
ans[k] = tree.query(i) + 1;
tree.update(i, ans[k]);
}
return ans;
}