algorithm - 查找相邻元素至少相差 k 的最长递增子序列

Question

给定一个数组 A尺寸n和一个数字 k , 找到最长递增子序列的大小(例如 B[] )，其中 B[i+1] >= B[i] + k .

2 <= n <= 10^6
A[i] <= 10^5
k <= 10^5

示例输入:

A = [1, 3, 1, 4, 5, 9, 12]
k = 2
The LIS in this case will be: [1, 3, 5, 9, 12]
Answer = 5

如何解决复杂问题 O(N * log(N)) (或更好)？我已经描述了我的 O(N^2 * log(N))方法如下:

我将使用类似于 std::multiset 的数据结构(在 C++ 中)。 std::multiset将确保 multiset 中的所有元素在任何时间点都将被排序。

我将制作一组对 std::multiset <pair <int, int> > V其中对中的第一个元素将是数组 A 中的元素第二个元素将是最长递增子序列的大小，使得 LIS 在该对的第一个元素处结束。此外，在每种情况下，多重集中的第一对将是 <-∞, 0> .

int answer() {

    multiset < pair < int, int> > V;
    V.insert(<-∞, 0>);
    final_answer = 1

    for (element e) in A {
        maximum_possible = 1

        for (pair p) in V {
            if (p.first > e - k)
                break;
            maximum_possible = max(p.second + 1, maximum_possible)
        }
        V.insert(<A[i], maximum_possible>)
        final_answer = max(final_answer, maximum_possible)
    }

    return final_answer;
}

Answer 1

您可以使用 LIS 的标准动态规划在 O(N^2) 中执行此操作: 唯一的变化是将 if 条件中的 nums[i] > nums[j] 改为 nums[i] - nums[j] >= K

    public int lengthOfLISAtLeastKUsingDP(int[] nums, int K) {
        int[] dp = new int[nums.length+1];
        Arrays.fill(dp, 1);
        int ans = 0;
        for ( int i = 0; i < nums.length; i++ ) {
            for ( int j = 0; j < i; j++ ) {
                if ( nums[i] - nums[j] >= K ) {
                    dp[i] = Math.max( dp[i], 1 + dp[j] );
                }
            }
            ans = Math.max( ans, dp[i] ); 
        }
        return ans;
    }

话虽如此，我相信您可以像这样在 O(N*log(N)) 中做到这一点:

1. 创建一个空列表。
2. 将第一个元素添加到列表中。
3. 遍历链表，如果遇到比链表最后一个元素大大于等于K的元素，则将其加入链表。
4. 如果不是，则在列表中对该元素进行二分查找，如果找到则无事可做。
5. 否则查看插入点。插入点大于或小于列表的大小。
6. 如果它大于 size 并且如果该元素与列表中最后一个元素之间的差异大于 K，则将其添加到列表中。
7. 如果插入点为零，则只替换第0个元素。
8. 但如果插入点不为零，则查看其左侧元素。如果它们的差值大于或等于 K，则将元素插入到那里。
9. 结果列表的大小就是答案。

public int lengthOfLISAtLeastK(int[] nums, int K) {
    if ( nums == null ) return 0;
    if ( nums.length <= 1 ) return nums.length;
    List<Integer> list = new ArrayList<Integer>(nums.length);
    list.add( 0, nums[0] );
    for ( int i = 1; i < nums.length; i++ ) {
        if ( nums[i] - list.get( list.size() - 1 ) >= K ) {
            list.add( nums[i] );
        } else  {
            int index = Collections.binarySearch( list, nums[i] );
            if ( index >= 0 && index < nums.length ) {
                list.set( index, nums[i] );
            } else {
                if ( -index - 1 > list.size() - 1 ) {
                    if ( nums[i] - list.get(list.size()-1) >= K ) {
                        list.add(nums[i]);
                    }
                } else {
                     if ( -index - 1 == 0 ) {
                        list.set(-index-1, nums[i]);
                    } else if ( nums[i] - list.get(-index-2) >= K ) {
                        list.set(-index-1, nums[i]);
                    }
                }
            }
        }
    }
    return list.size();
}