1964. 找出到每个位置为止最长的有效障碍赛跑路线

考点

• 最长单调不减序列

思路

1. 问题描述（Problem Restatement）

给定一个长度为 \(n\) 的整数数组 \[ \texttt{obstacles} = [a_0, a_1, \dots, a_{n-1}] \] 对于每一个位置 \(i\)，需要计算：

以 \(a_i\) 作为结尾元素的、最长的“有效障碍赛路线”长度。

其中，“有效障碍赛路线”满足：

1. 所选元素的索引严格递增（保持原数组顺序）；

2. 数值是单调不减的，即 \[ a_{i_1} \le a_{i_2} \le \dots \le a_{i_k} \]

3. 序列必须包含当前元素 \(a_i\)，且 \(i_k = i\)。

---

2. 问题建模（Modeling）

2.1 与经典问题的关系

该问题可以建模为：

对每个位置 \(i\)，求“以 \(i\) 为结尾的最长非严格递增子序列（LNDS）长度”。

这是经典 最长递增子序列（LIS） 问题的一个变体：

问题	约束
LIS	严格递增（<）
本题	非严格递增（\(\le\)）
LIS（经典）	只求全局最优
本题	要求每个位置的局部最优（以 \(i\) 结尾）

---

2.2 状态定义（核心思想）

引入一个辅助数组： \[ f[k] = \text{当前已处理前缀中，长度为 } k+1 \text{ 的非递减子序列的最小可能结尾值} \] 该数组具有两个关键性质：

1. f 始终是单调不减的；
2. f.size() 等于当前前缀能达到的 最长非递减子序列长度。

---

3. 算法思路（Algorithmic Strategy）

3.1 核心贪心思想

对数组 obstacles 从左到右扫描，每次处理一个新元素 \(x\)：

• 希望将 \(x\) 放到一个尽可能“靠右”的位置，使得：
  • 前面的结尾值 \(\le x\)
  • 从而构造一个更长、但结尾尽量小的非递减序列

---

3.2 二分查找定位位置

由于 f 是单调不减的，可以对其使用二分查找： \[ \text{pos} = \min \{ k \mid f[k] > x \} \] 在 C++ 中，这正是：

upper_bound(f.begin(), f.end(), x)

含义是：

• 找到第一个 严格大于 \(x\) 的位置
• 保证“\(\le x\)”的非递减条件成立

---

3.3 状态转移与答案计算

设： \[ \text{pos} = \texttt{it} - f.begin() \] 则有：

• 以当前 \(x\) 结尾的最长长度： \[ \boxed{\text{len} = \text{pos} + 1} \]

随后：

• 若 it == f.end()：说明 \(x\) 可以延长当前最长序列，执行 push_back
• 否则：用 \(x\) 替换 f[pos]，以获得更优（更小结尾）的同长度序列

⚠️ 关键点：

答案永远是 pos + 1，而不是 f.size() 因为 f 表示的是“全局 tails 状态”，而非“以当前位置结尾”的结果。

---

4. 正确性说明（Why It Works）

1. 贪心正确性 对于同一长度的非递减子序列，保留结尾最小的方案，总是更有利于后续扩展。
2. 二分查找的合法性 由于 f 单调不减，可以保证 upper_bound 找到的正是“最长可行前缀”。
3. 逐点最优性 在处理第 \(i\) 个元素时，pos + 1 精确表示“以 \(i\) 为结尾”的最优长度，满足题意。

---

5. 复杂度分析（Complexity）

• 时间复杂度： \[ O(n \log n) \] 每个元素一次二分查找

• 空间复杂度： \[ O(n) \] 维护 f 与 ans 数组

---

6. AC代码

class Solution {
public:
    static const int maxn = 1e5 + 5;
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        vector<int> f, ans;
        for (int& x : obstacles) {
            auto it = upper_bound(f.begin(), f.end(), x);
            int len = it - f.begin() + 1;
            if (it == f.end())
                f.push_back(x);
            else
                *it = x;
            ans.push_back(len);
        }
        return ans;
    }
};