LeetCode in Kotlin
2407. Longest Increasing Subsequence II
Hard
You are given an integer array nums and an integer k.
Find the longest subsequence of nums that meets the following requirements:
- The subsequence is strictly increasing and
- The difference between adjacent elements in the subsequence is at most
k.
Return the length of the longest subsequence that meets the requirements.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.
Example 2:
Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.
Example 3:
Input: nums = [1,5], k = 1
Output: 1
Explanation: The longest subsequence that meets the requirements is [1]. The subsequence has a length of 1, so we return 1.
Constraints:
1 <= nums.length <= 1051 <= nums[i], k <= 105
Solution
@Suppress("NAME_SHADOWING")
class Solution {
private class SegTree(private val n: Int) {
private val arr: IntArray = IntArray(2 * n)
fun query(l: Int, r: Int): Int {
var l = l
var r = r
l += n
r += n
var ans = 0
while (l < r) {
if (l and 1 == 1) {
ans = ans.coerceAtLeast(arr[l])
l += 1
}
if (r and 1 == 1) {
r -= 1
ans = ans.coerceAtLeast(arr[r])
}
l = l shr 1
r = r shr 1
}
return ans
}
fun update(i: Int, `val`: Int) {
var i = i
i += n
arr[i] = `val`
while (i > 0) {
i = i shr 1
arr[i] = arr[2 * i].coerceAtLeast(arr[2 * i + 1])
}
}
}
fun lengthOfLIS(nums: IntArray, k: Int): Int {
var max = 0
for (n in nums) {
max = max.coerceAtLeast(n)
}
val seg = SegTree(max)
var ans = 0
var i = 0
while (i < nums.size) {
var n = nums[i]
n -= 1
val temp = seg.query(0.coerceAtLeast(n - k), n) + 1
ans = ans.coerceAtLeast(temp)
seg.update(n, temp)
i++
}
return ans
}
}