下面用二分优化的 LIS 函数的时间复杂度为：
int LIS(vector<int> & nums) {
int n = nums.size();
vector<int> tail; tail.push_back(INT_MIN);
for (int i = 0; i < n; i++) {
int x = nums[i], l = 0, r = tail.size();
while (l < r) {
int mid = (l + r) / 2;
if (tail[mid] < x) l = mid + 1; else r = mid;
}
if (r == tail.size()) tail.push_back(x); else tail[r] = x;
}
return tail.size() - 1;
}
- A. O(n)
- B. O(n²)
- C. O(n log n)
- D. O(log n)
正确答案：C