Hard

题目描述

给你一个整数数组 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 <= 10^5
  • 1 <= nums[i], k <= 10^5

解题思路

这道题是经典最长递增子序列（LIS）问题的变种，增加了相邻元素差值不超过 k 的约束。

核心思路： 使用动态规划 + 线段树优化。定义 dp[val] 表示以值 val 结尾的最长子序列长度。

算法步骤：

  1. 遍历数组中的每个元素 num
  2. 对于当前元素 num，它可以接在值为 [num-k, num-1] 范围内的任意元素后面
  3. 查询线段树在区间 [num-k, num-1] 内的最大 dp 值，记为 maxLen
  4. 更新 dp[num] = maxLen + 1
  5. 在线段树中更新位置 num 的值为 dp[num]

为什么用线段树：

  • 需要频繁进行区间查询最大值和单点更新操作
  • 暴力方法时间复杂度为 O(n²)，会超时
  • 线段树可以将区间查询和单点更新都优化到 O(log n)

优化细节：

  • 由于值域较大（最大 10^5），直接建立线段树
  • 初始化所有 dp 值为 0，表示该值还未出现过

时间复杂度：O(n log V)，其中 V 是值域大小 空间复杂度：O(V)

代码实现

class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        int maxVal = *max_element(nums.begin(), nums.end());
        vector<int> tree(4 * maxVal + 4, 0);
        
        function<void(int, int, int, int, int)> update = [&](int node, int start, int end, int idx, int val) {
            if (start == end) {
                tree[node] = val;
            } else {
                int mid = (start + end) / 2;
                if (idx <= mid) {
                    update(2 * node, start, mid, idx, val);
                } else {
                    update(2 * node + 1, mid + 1, end, idx, val);
                }
                tree[node] = max(tree[2 * node], tree[2 * node + 1]);
            }
        };
        
        function<int(int, int, int, int, int)> query = [&](int node, int start, int end, int l, int r) -> int {
            if (r < start || end < l) {
                return 0;
            }
            if (l <= start && end <= r) {
                return tree[node];
            }
            int mid = (start + end) / 2;
            return max(query(2 * node, start, mid, l, r),
                      query(2 * node + 1, mid + 1, end, l, r));
        };
        
        int ans = 0;
        for (int num : nums) {
            int left = max(1, num - k);
            int right = num - 1;
            int maxLen = (right >= left) ? query(1, 1, maxVal, left, right) : 0;
            int newLen = maxLen + 1;
            update(1, 1, maxVal, num, newLen);
            ans = max(ans, newLen);
        }
        
        return ans;
    }
};

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        max_val = max(nums)
        tree = [0] * (4 * max_val + 4)
        
        def update(node, start, end, idx, val):
            if start == end:
                tree[node] = val
            else:
                mid = (start + end) // 2
                if idx <= mid:
                    update(2 * node, start, mid, idx, val)
                else:
                    update(2 * node + 1, mid + 1, end, idx, val)
                tree[node] = max(tree[2 * node], tree[2 * node + 1])
        
        def query(node, start, end, l, r):
            if r < start or end < l:
                return 0
            if l <= start and end <= r:
                return tree[node]
            mid = (start + end) // 2
            return max(query(2 * node, start, mid, l, r),
                      query(2 * node + 1, mid + 1, end, l, r))
        
        ans = 0
        for num in nums:
            left = max(1, num - k)
            right = num - 1
            max_len = query(1, 1, max_val, left, right) if right >= left else 0
            new_len = max_len + 1
            update(1, 1, max_val, num, new_len)
            ans = max(ans, new_len)
        
        return ans

public class Solution {
    public int LengthOfLIS(int[] nums, int k) {
        int maxVal = nums.Max();
        int[] tree = new int[4 * maxVal + 4];
        
        void Update(int node, int start, int end, int idx, int val) {
            if (start == end) {
                tree[node] = val;
            } else {
                int mid = (start + end) / 2;
                if (idx <= mid) {
                    Update(2 * node, start, mid, idx, val);
                } else {
                    Update(2 * node + 1, mid + 1, end, idx, val);
                }
                tree[node] = Math.Max(tree[2 * node], tree[2 * node + 1]);
            }
        }
        
        int Query(int node, int start, int end, int l, int r) {
            if (r < start || end < l) {
                return 0;
            }
            if (l <= start && end <= r) {
                return tree[node];
            }
            int mid = (start + end) / 2;
            return Math.Max(Query(2 * node, start, mid, l, r),
                           Query(2 * node + 1, mid + 1, end, l, r));
        }
        
        int ans = 0;
        foreach (int num in nums) {
            int left = Math.Max(1, num - k);
            int right = num - 1;
            int maxLen = (right >= left) ? Query(1, 1, maxVal, left, right) : 0;
            int newLen = maxLen + 1;
            Update(1, 1, maxVal, num, newLen);
            ans = Math.Max(ans, newLen);
        }
        
        return ans;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var lengthOfLIS = function(nums, k) {
    const maxVal = Math.max(...nums);
    const tree = new Array(4 * maxVal).fill(0);
    
    function update(node, start, end, idx, val) {
        if (start === end) {
            tree[node] = Math.max(tree[node], val);
        } else {
            const mid = Math.floor((start + end) / 2);
            if (idx <= mid) {
                update(2 * node, start, mid, idx, val);
            } else {
                update(2 * node + 1, mid + 1, end, idx, val);
            }
            tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
        }
    }
    
    function query(node, start, end, l, r) {
        if (r < start || end < l) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        const mid = Math.floor((start + end) / 2);
        return Math.max(
            query(2 * node, start, mid, l, r),
            query(2 * node + 1, mid + 1, end, l, r)
        );
    }
    
    let result = 0;
    
    for (const num of nums) {
        const left = Math.max(1, num - k);
        const right = num - 1;
        
        let maxLen = 0;
        if (left <= right) {
            maxLen = query(1, 1, maxVal, left, right);
        }
        
        const newLen = maxLen + 1;
        update(1, 1, maxVal, num, newLen);
        result = Math.max(result, newLen);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log V)n 为数组长度，V 为值域大小，每个元素需要进行线段树查询和更新操作
空间复杂度O(V)线段树需要 4V 的空间存储节点

相关题目