Hard

题目描述

你想要建造一些障碍赛跑路线。给你一个下标从 0 开始、长度为 n 的整数数组 obstacles，其中 obstacles[i] 表示第 i 个障碍的高度。

对于每个介于 0 和 n - 1 之间（包括 0 和 n - 1）的下标 i，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：

  • 你可以选择下标 0 到 i 之间（包括 0 和 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]

提示：

  • n == obstacles.length
  • 1 <= n <= 10^5
  • 1 <= obstacles[i] <= 10^7

解题思路

这道题本质上是求最长非严格递增子序列（LIS 变种），对于每个位置 i，我们需要找出以 obstacles[i] 结尾的最长非递减子序列长度。

核心思路：

  1. 维护一个数组 tails，其中 tails[len-1] 表示长度为 len 的非递减子序列的最小结尾值
  2. 对于每个障碍 obstacles[i]，使用二分查找在 tails 中找到第一个大于 obstacles[i] 的位置
  3. 如果找到这样的位置，说明可以延长现有序列；否则开始一个新的更长序列
  4. 更新 tails 数组并记录当前位置的答案

关键点：

  • 由于允许相等高度，我们需要找第一个大于当前元素的位置（而不是大于等于）
  • 使用 upper_bound 或手写二分查找来实现
  • tails 数组始终保持有序，便于二分查找

时间复杂度分析：

  • 对每个元素进行一次二分查找：O(n log n)
  • 整体时间复杂度：O(n log n)，空间复杂度：O(n)

这种方法相比动态规划的 O(n²) 解法有显著性能提升，特别适合处理大规模数据。

代码实现

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        vector<int> tails;
        vector<int> result;
        
        for (int obstacle : obstacles) {
            auto it = upper_bound(tails.begin(), tails.end(), obstacle);
            int pos = it - tails.begin();
            
            if (it == tails.end()) {
                tails.push_back(obstacle);
            } else {
                *it = obstacle;
            }
            
            result.push_back(pos + 1);
        }
        
        return result;
    }
};

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        import bisect
        
        tails = []
        result = []
        
        for obstacle in obstacles:
            pos = bisect.bisect_right(tails, obstacle)
            
            if pos == len(tails):
                tails.append(obstacle)
            else:
                tails[pos] = obstacle
            
            result.append(pos + 1)
        
        return result

public class Solution {
    public int[] LongestObstacleCourseAtEachPosition(int[] obstacles) {
        var tails = new List<int>();
        var result = new int[obstacles.Length];
        
        for (int i = 0; i < obstacles.Length; i++) {
            int obstacle = obstacles[i];
            int pos = BinarySearch(tails, obstacle);
            
            if (pos == tails.Count) {
                tails.Add(obstacle);
            } else {
                tails[pos] = obstacle;
            }
            
            result[i] = pos + 1;
        }
        
        return result;
    }
    
    private int BinarySearch(List<int> tails, int target) {
        int left = 0, right = tails.Count;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

/**
 * @param {number[]} obstacles
 * @return {number[]}
 */
var longestObstacleCourseAtEachPosition = function(obstacles) {
    const n = obstacles.length;
    const result = new Array(n);
    const tails = [];
    
    for (let i = 0; i < n; i++) {
        const height = obstacles[i];
        
        // Binary search for the position to insert/replace
        let left = 0, right = tails.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] <= height) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // If left equals tails.length, we append
        if (left === tails.length) {
            tails.push(height);
        } else {
            tails[left] = height;
        }
        
        result[i] = left + 1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)对每个元素进行二分查找
空间复杂度O(n)tails 数组最多存储 n 个元素

相关题目