2407. 最长递增子序列 II 线段树

2407. 最长递增子序列 II 

给你一个整数数组 nums 和一个整数 k 。

找到 nums 中满足以下要求的最长子序列：

• 子序列 严格递增
• 子序列中相邻元素的差值 不超过 k 。

请你返回满足上述要求的 最长子序列 的长度。

子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。

示例 1：

输入：nums = [4,2,1,4,3,4,5,8,15], k = 3
输出：5
解释：
满足要求的最长子序列是 [1,3,4,5,8] 。
子序列长度为 5 ，所以我们返回 5 。
注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。

示例 2：

输入：nums = [7,4,5,1,8,12,4,7], k = 5
输出：4
解释：
满足要求的最长子序列是 [4,5,8,12] 。
子序列长度为 4 ，所以我们返回 4 。

示例 3：

输入：nums = [1,5], k = 1
输出：1
解释：
满足要求的最长子序列是 [1] 。
子序列长度为 1 ，所以我们返回 1 。

提示：

• 1 <= nums.length <= 1e5
• 1 <= nums[i], k <= 1e5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，线段树一次搞定

方法：线段树

 其实这题这么小范围，不用动态开点也行，不用动态开点的方式不会写，所以一律都用动态开点了，就是写起来长了点。

1. 从[num-k,num-1] 范围找到之前的最长子序列

2. 当前子序列是之前子序列长度+1

3. 添加当前元素到线段树

class Solution {
        public int lengthOfLIS(int[] nums, int k) {
            Line line = new Line();
            int ans = 0;
            for(int num:nums){
                int max = line.getMax(num-k,num-1);
                ans = Math.max(max+1,ans);
                line.setVal(num,max+1);
            }
            return ans;
        }
 
        class Line{
            int start;
            int end;
            Line left;
            Line right;
            int maxVal;
            public Line(){
                start = 0;
                end = (int)(1e6+1);
            }
 
            public Line(int start, int end){
                this.start = start;
                this.end = end;
            }
 
            public int getMax(int L,int R){
                if(start>R||endreturn 0;
                if(start>=L&&end<=R) return maxVal;
                int m1 = left!=null?left.getMax(L,R):0;
                int m2 = right!=null?right.getMax(L,R):0;
                return Math.max(m1,m2);
            }
 
            public void setVal(int pos, int V){
                if(start>pos || endreturn;
                maxVal = Math.max(V,maxVal);
                if(start==end) return;
 
                int mid = (end-start)/2+start;
                if(pos<=mid){
                    if(left == null) left = new Line(start,mid);
                    left.setVal(pos,V);
                }else{
                    if(right == null) right = new Line(mid+1,end);
                    right.setVal(pos,V);
                }
            }
        }
 
    }