1964. 找出到每个位置为止最长的有效障碍赛跑路线 - Kotlin 二分查找 最长单调子序列

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

思路

本题和354. 俄罗斯套娃信封问题 是相同类型的题目，即最长单调子序列问题，相比俄罗斯套娃问题要求信封的最长递增子序列，本题的题意中要求的是障碍物的最长不递减子序列

解决最长单调子序列的一个朴素的DP做法是：用一个DP数组记录以某个元素为末尾的最长单调子序列长度，遍历到元素i时，遍历DP数组中位于i之前的所有元素，对于小于i的所有元素，都可以在以其结尾的子序列后再加上一个i形成一个新的子序列，因此以i结尾的最长子序列长度就是这些元素对应的最长子序列长度的最大值+1

这种做法因为每次遍历到i时都要用j再去遍历i之前的所有元素，因此时间复杂度是的，在某些情况下（比如这两道题）会因为数据量过大而TLE，尤其是[1,2,3,4,…,999999]这种本身就递增的合法序列

另一个做法是基于二分查找的，他基于这样的一个有些“贪心”的推论：如果当我们构造一个长度固定的子序列时，每次都尽可能地选较小的值去构造的话（比如1,2,3,4,5，构造长度为4的子序列时我们只考虑1234的情况，而不考虑1235的情况），那么对于一个长度为i的子序列，其末尾元素的大小必然是大于一个长度为i-1的子序列的末尾元素的大小的

我们用一个数组lastOfSeq记录不同长度下子序列的末尾元素大小，其中lastOfSeq[i]=j意味着长度为i+1的子序列的末尾元素为j，则lastOfSeq.size本身则意味着整个数组的最长递增子序列长度了

基于上面的推论，我们可以假设这个数组是有序的，即对于任何i>j，都有lastOfSeq[i]>=lastOfSeq[j]，那么我们就可以对这个数组二分查找。

当我们遍历到一个元素i时，我们通过二分查找可以查找到数组中首个大于该元素的元素j

• 当j>i时，说明j的前一个元素恰好小于i，j的前一个元素恰好可以再接上i形成一个更长的子序列，此时新的子序列长度为j的索引+1，由于i小于j，而j的含义为：长度为j的索引+1的子序列的末尾元素，其最小值为j，我们可将j的值替换为i
• 在替换完毕后，i的索引+1即为以i结尾的最长子序列长度

复杂度

• 时间复杂度:
  

• 空间复杂度:
  

Code

class Solution {
    fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
        val lastOfSeq = ArrayList<Int>()
        var ans = IntArray(obstacles.size)
        for ((index, obstacle) in obstacles.withIndex()) {
            if (lastOfSeq.size == 0 || obstacle >= lastOfSeq[lastOfSeq.size - 1]) {
                lastOfSeq.add(obstacle)
                ans[index] = lastOfSeq.size
            } else {
                var next=binSearch(lastOfSeq, obstacle)
                lastOfSeq.set(next, obstacle)
                ans[index] = next+1
            }
        }
        return ans
    }

    fun binSearch(f: List<Int>, target: Int): Int {
        var left = 0
        var right = f.size - 1
        var mid: Int

        while (left <= right) {
            mid = (right - left) / 2 + left
            if (f[mid] <= target) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return left
    }
}