问题的拆解、抽象与转化

摘要: 将新问题转化为已经解决过的老问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

当我们拿到一个新问题时，一个重要的思想是将其转化为已经解决过的老问题。具体的转化方法需要结合具体问题，比较有技巧性。

一个常见的思路是问题拆解，将问题拆成若干步，每步一个输入一个输出，然后串联起来，其中每一步都是一个已经解决过的经典问题。重排链表问题是一个例子，参考文章问题拆解的威力，重排链表问题。

问题抽象也是一个常见的思路，拿到的问题可能有具体的场景，描述非常冗长。但是如果去掉具体场景，把问题描述为一个抽象问题，发现这个抽象问题是一个经典问题或者已经解决过的问题。这种情况常见于图算法的问题，原始问题非常复杂，根据场景信息建图就是一个抽象的过程，一旦正确建图，会发现就是一个经典问题，文章 二分图匹配：最大匹配，匈牙利算法 中的棋盘覆盖问题是一个例子。

问题转化是一个更广泛的技巧，比如将问题换一种方式描述、或者构造一些辅助结构，使得原问题的答案等价于辅助结构上的另一个问题。只要转化后的问题是一个经典问题或已解决问题，甚至只是比原问题更容易解决，那这步转化就是有价值的。比如在文章 冒泡排序平均需要跑多少趟：拉马努金Q函数初探 中，我们讨论冒泡排序平均趟数，通过构造逆序表，将问题转化为更好解决的逆序表的最大值的问题。

题目

• 2779. 数组的最大美丽值

给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。

在一步操作中，你可以执行下述指令：

• 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
• 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。

数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 nums 执行上述操作任意次后，返回数组可能取得的 最大 美丽值。

注意：你 只 能对每个下标执行 一次 此操作。

数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。

提示：

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

示例 1：
输入：nums = [4,6,1,2], k = 2
输出：3
解释：在这个示例中，我们执行下述操作：

• 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
• 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。
  执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。
  可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

示例 2：
输入：nums = [1,1,1,1], k = 10
输出：4
解释：在这个示例中，我们无需执行任何操作。
数组 nums 的美丽值是 4（整个数组）。

题解

算法：转化为区间问题

对于每个 $nums[i]$，都可以取到 $[nums[i] - k, nums[i] + k]$ 这个范围。

如果我们将 $nums$ 中的 $n$ 个元素视为 $n$ 个区间，那么原问题就相当于问这 $n$ 个区间最多可以选出多少个，使得选出的区间具有公共重合的部分。

而这是区间问题中的一个经典问题，解法很多，下面我们用扫描线算法解决。关于用扫描线算法处理区间问题，可以参考文章 扫描线算法处理一系列区间上的统计问题。

将每个区间端点视为一个事件，具有两个属性，一个是位置 x，一个是左端点标记 left，若为左端点，则标记值为 0，否则为 1。

在对事件排序时，若位置相同，则左端点排在前面，这样在统计重合部分的区间数时，一区间右端点与另一区间左端点重合的情况可以统计上。于是事件的定义如下：

class Event:
    def __init__(self, x, left):
        self.x = x
        self.left = left

    def __lt__(self, other):
        if self.x == other.x:
            return self.left < other.left
        return self.x < other.x

将事件排序后，按顺序枚举每个事件，过程中记录重合的区间数 s，若当前事件为左端点，则 s += 1，同时更新答案 ans = max(ans, s)，若为右端点，则 s -= 1。

按顺序枚举完成后，ans 即为具有重合部分的最多区间数。

代码 (Python)

class Event:
    def __init__(self, x, left):
        self.x = x
        self.left = left

    def __lt__(self, other):
        if self.x == other.x:
            return self.left < other.left
        return self.x < other.x

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        events = []
        for x in nums:
            events.append(Event(x - k, 0))
            events.append(Event(x + k, 1))
        events.sort()
        s = 0
        ans = 0
        for e in events:
            if e.left == 0:
                s += 1
                ans = max(ans, s)
            else:
                s -= 1
        return ans

---