题目分析

本题是周赛的第四题，题意比较简单，和Leetcode300题非常相似，主要考察小伙伴们一题多解的能力，这个也是我写这些博客的目的。在很多题目里，我都会写出某个题的多种解法，如果第300题，小伙伴们只掌握了单调栈+二分的做法，那么本题是无法求解的。小伙伴们可以去看一下最长递增子序列的其他解法，然后试着写出本题。

树状数组

这个题目的思路就不做过多介绍了，可以看一下最长递增子序列的分析。

这里主要介绍一下本题和第300题的区别，第300题不限制递增序列中，相邻两个元素的距离。因此使用树状数组和线段树查找时，直接找从0到x - 1的元素最大值即可。

本题的难度大的原因在于，要寻找从x - k到x - 1的元素最大值。因为本题的元素从1开始，如果k > x，则寻找从1开始的元素最大值。，即query(max(1, x - k), x - 1)。

本题使用树状数组的难点在于，树状数组善于计算从0到x的统计意义(如求和、最大值等)，如果从m到x的求和，可以使用0到x的求和减去0到m-1的求和。但是最大值不可以这么做。

因此如何使用树状数组求m到x的最大值，即query(lowIdx, highIdx)如何实现是我们需要学习的。

首先看一下树状数组中的tree，其实就是某些原始数组arr的统计表示。我们当然可以重新new一个数组表示原始数组。我默认看到这里的小伙伴是学习过树状数组的，下面直接讲专业术语。

如果highIdx - lowBit(highIdx) >= lowIdx，说明tree[highIdx]中的原始在查找的区间内。否则tree[highIdx]表示的元素中，有部分元素小于lowIdx区间，如果这部分元素决定着tree[highIdx]的最大值，那么查询到的结果是不正确的。

如果highIdx - lowBit(highIdx) >= lowIdx，则highIdx可以更新到highIdx - lowBit(highIdx)。否则只能查询原始数组中highIdx的值arr[highIdx]，然后将highIdx - 1，继续查询。

一共有log(n)位，每一次-1后，低位都是1，因此又需要log(n)的时间去减lowBit。因此算法的时间复杂度为$ O(nlog^2(n)) $，空间复杂度为O(n)，n为数组的最大值。

class Solution {
    private int[] tree;

    private int[] arr;

    public int lengthOfLIS(int[] nums, int k) {
        int res = 0;
        int max = Arrays.stream(nums).max().getAsInt();
        tree = new int[max + 1];
        arr = new int[max + 1];
        for (int x : nums) {
            int cnt = query(Math.max(x - k, 1), x - 1) + 1;
            res = Math.max(res, cnt);
            add(x, cnt);
            arr[x] = cnt;
        }
        return res;
    }

    private void add(int idx, int val) {
        for (; idx < tree.length; idx += lowBit(idx)) {
            tree[idx] = Math.max(tree[idx], val);
        }
    }

    private int query(int lowIdx, int highIdx) {
        int res = 0;
        while (lowIdx <= highIdx) {
            for (; highIdx - lowBit(highIdx) >= lowIdx; highIdx -= lowBit(highIdx)) {
                res = Math.max(res, tree[highIdx]);
            }
            res = Math.max(res, arr[highIdx--]);
        }
        return res;
    }

    private int lowBit(int x) {
        return x & -x;
    }
}

线段树

本题的最优解是线段树，线段树本身就提供查询某一段区间的统计意义，因此直接看代码即可。

对线段树不熟悉的小伙伴，可以参考线段树

算法的时间复杂度为$ O(nlog(n)) $，空间复杂度为O(n)。

class Solution {
    private int[] tree;

    public int lengthOfLIS(int[] nums, int k) {
        int res = 0;
        int max = Arrays.stream(nums).max().getAsInt();
        tree = new int[max * 4];
        for (int x : nums) {
            int cnt = query(0, Math.max(x - k, 0), x - 1, 0, max) + 1;
            res = Math.max(res, cnt);
            add(0, x, cnt, 0, max);
        }
        return res;
    }

    private void add(int node, int idx, int val, int left, int right) {
        if (left == right) {
            tree[node] = val;
            return;
        }
        int mid = (left + right) >> 1;
        int leftNode = node * 2 + 1;
        int rightNode = leftNode + 1;
        if (idx <= mid) {
            add(leftNode, idx, val, left, mid);
        } else {
            add(rightNode, idx, val, mid + 1, right);
        }
        tree[node] = Math.max(tree[leftNode], tree[rightNode]);
    }

    private int query(int node, int leftRange, int rightRange, int left, int right) {
        if (leftRange == left && rightRange == right) {
            return tree[node];
        }
        int mid = (left + right) >> 1;
        int leftNode = node * 2 + 1;
        int rightNode = leftNode + 1;
        if (rightRange <= mid) {
            return query(leftNode, leftRange, rightRange, left, mid);
        } else if (leftRange > mid) {
            return query(rightNode, leftRange, rightRange, mid + 1, right);
        } else {
            return Math.max(query(leftNode, leftRange, mid, left, mid), query(rightNode, mid + 1, rightRange, mid + 1, right));
        }
    }
}

刷题总结

树状数组和线段树经常出现在一些比赛中，难度不大，有固定的代码模板。不推荐小伙伴们背模板，但是每天写一遍，一星期就可以熟练写出来线段树的代码了。