【LeetCode-C】 Knowledges Feb

差分数组（Difference Array）

差分数组（Difference Array）是一种用于高效处理数组区间修改操作的数据结构或技巧。它的核心优势在于，能将需要对原数组某个区间内所有元素进行加减操作的时间复杂度从常规方法的 O(n) 降低到 O(1) 。

下面这个表格可以帮助你快速抓住差分数组的核心要点。

特性	常规方法	差分数组方法
核心操作	直接遍历区间修改每个元素	仅修改区间两端的差分值
修改区间时间复杂度	O(n)	O(1)
适用场景	单次或少量修改	频繁进行区间加减操作
查询操作	单点查询O(1)，区间查询O(n)	需要还原原数组，查询效率较低

差分数组详解

💡 基本概念

差分数组是一个与原数组长度相同的数组，其中每个位置存储的是原数组当前元素与前一个元素的差值。

给定一个原始数组 arr，其差分数组 diff 的定义如下：

diff[0] = arr[0]（当 i = 0 时）
diff[i] = arr[i] - arr[i-1]（当 i ≥ 1 时）

例如，对于原始数组 arr = [3, 5, 7, 9, 11]，其对应的差分数组为 diff = [3, 2, 2, 2, 2] 。

🔄 工作原理

差分数组的关键在于，对原数组的区间修改，可以转化为对差分数组仅两个端点的修改 。

假设你需要对原数组 arr 的区间 [L, R]（包含L和R）内的每个元素都加上一个值 k，使用差分数组只需两步：

diff[L] += k
if (R + 1 < arr.length) diff[R + 1] -= k （如果 R+1 没有超出数组边界）

原理说明：

第一步 diff[L] += k 意味着从位置 L 开始，之后所有位置的原数组值在通过差分数组还原时都会自动加上 k。
第二步在 diff[R+1] 处减去 k，是为了抵消对区间 [R+1, ...] 的影响，使得只有区间 [L, R] 内的元素受到加 k 的影响。

修改完成后，通过对差分数组进行前缀和运算即可还原出修改后的原数组：

arr[0] = diff[0]
arr[i] = arr[i-1] + diff[i] （对于 i ≥ 1）

🛠️ 代码实现

差分数组通常被封装成一个工具类，以便使用。以下是一个典型的Java实现示例：

// 差分数组工具类
class Difference {
    private int[] diff; // 差分数组

    /* 输入一个初始数组，构造差分数组 */
    public Difference(int[] nums) {
        diff = new int[nums.length];
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i-1];
        }
    }

    /* 给闭区间 [i, j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i-1] + diff[i];
        }
        return res;
    }
}

💻 实际应用场景

差分数组特别适用于以下情况：

大量区间修改操作：问题需要对数组进行多次区间增减操作。
最后统一查询：所有修改操作完成后，才需要查询最终结果（只需还原一次）。
离线处理：可以预先记录所有修改操作，最后一次性应用差分并还原。

典型力扣（LeetCode）例题：

1109. 航班预订统计 ：根据一系列航班预订记录（每个记录表示在某个区间内的航班上都预订了若干座位），计算每个航班最终的座位总数。
1094. 拼车 ：判断一辆车能否在不超过容量的情况下，完成所有乘客的接送（乘客在特定区间上车和下车）。
370. 区间加法 ：模拟对一个数组进行多次区间加法操作，最后返回整个数组。

⚠️ 优点与局限

优点：将 O(n) 的区间修改操作降低到 O(1)，实现简单，概念清晰。
局限：单点查询或区间查询效率较低，需要 O(n) 时间还原前缀和。如果查询操作非常频繁，可能需要结合树状数组或线段树等更高级的数据结构。

总结

简单来说，差分数组就像一位聪明的“调度员”。当需要对一大段连续区域进行统一调整时，它不急于逐个处理，而是先在起点做个“开始调整”的标记，在终点后做个“结束调整”的标记。等所有调整指令都下达完毕后，再一次性从头到尾执行，过程中根据标记决定何时开始加、何时开始减，从而高效地得到最终结果。这种“化整为零”的思路，在处理频繁区间修改的问题时非常高效。

希望这些解释能帮助你理解差分数组。如果你对上面提到的具体例题或代码实现有进一步的疑问，我可以再详细展开。

连通图

在 PlantUML 中，如果你希望文本内容保持在同一行显示，避免自动换行或手动换行，核心在于不要使用换行符，并可以利用一些语法技巧来明确意图。以下是具体的方法和说明。

💡 核心原则：避免换行符

在 PlantUML 中，最简单的强制文本在同一行的方法就是确保你的文本字符串内部不包含换行符 \n。

正确做法：直接在消息文本或标签中书写连续的文字，不使用 \n。
```
@startuml
Alice -> Bob: 这是一条非常长的消息但希望它保持在同一行显示尽管它可能很长很长
@enduml
```
在这种情况下，PlantUML 的渲染引擎会尝试根据图表布局自动处理文本显示。如果文本过长，它可能会根据可用空间自动换行，这与文本字符串本身是否包含换行符是不同的处理逻辑。
避免做法：不要使用 \n 进行主动换行。搜索结果中多次提到 \n 用于创建多行文本，但这与你的需求正好相反。

🛠️ 其他相关技巧

使用 as 关键字定义别名 对于参与者（Participant）或其他元素，如果名称很长但又希望在使用时保持一行显示，可以先用 as 关键字定义一个简短的别名，之后在消息中引用这个别名。
```
@startuml
participant "这是一个非常长的参与者名称" as ShortName
Alice -> ShortName: 消息给长名称参与者
@enduml
```
这样，在消息线上显示的就是简洁的 ShortName，而不是一长串文字。
注意组合消息块内的文本 当在 alt、loop、group 等组合消息块内书写文本时，同样遵循上述原则。块内的标题文字会自动在一行内显示。
```
@startuml
Alice -> Bob: 请求
alt 这是一个备选流程的说明
    Bob -> Alice: 响应
end
@enduml
```
这里的 这是一个备选流程的说明 会作为一行标题显示。
关于自动换行与图表布局 需要理解的是，即使文本中没有 \n，如果文本长度超过了 PlantUML 渲染引擎为当前图表元素分配的宽度，引擎可能会为了整体美观而自动换行。这通常由内置的布局算法决定。
- 你可以尝试通过调整文本长度，或利用 skinparam 命令调整全局样式（如字体大小等）来间接影响布局，但 PlantUML 没有直接禁止自动换行的参数。

💎 总结

要让 PlantUML 中的文本保持在同一行，关键是书写连续的文本字符串，避免使用 \n 换行符。对于长名称，使用 as 关键字定义别名是一个有效的简化方法。

希望这些信息能帮助你更好地控制 PlantUML 图表中的文本显示！如果你在特定场景下遇到问题，例如消息文本过长被自动截断，可以提供更多细节，我们可以一起探讨有没有更具体的解决方案。