leetcode 周赛 476 - 从高级线段树到简单前缀和

零、背景

LeetCode周赛476的第四题，表面上看是一个需要高级数据结构的区间查询问题，但实际上只需要简单的前缀和就能解决。

我在解题时犯了一个典型的错误：被问题的表面复杂度迷惑，忽略了本质的简单性。
第一反应选择了高级线段树解法，等实现完成时，已经有超过一百名选手用更简单的方法通过了这道题。

这次经历让我深刻反思：在算法竞赛中，识别问题的本质比掌握复杂的算法更重要。

题目分布：

• A: 贪心算法（简单）
• B: 栈的应用（中等）
• C: 数位动态规划（中等）
• D: 前缀和/莫队算法/高级线段树（困难）

最终排名：178
代码仓库：https://github.com/tiankonguse/leetcode-solutions
时间分配：前三题12分钟，第四题耗时较长导致排名下降

一、三元素表达式的最大值

题意：给定一个数组，任意选择三个不同下标 i, j, k，求表达式 arr[i] + arr[j] - arr[k] 的最大值。

思路：贪心算法

要使表达式值最大，需要：

• arr[i] 尽可能大
• arr[j] 尽可能大
• arr[k] 尽可能小

具体实现：

1. 对数组进行排序
2. 取最大的两个数和最小的一个数
3. 计算表达式：max1 + max2 - min

时间复杂度：O(n log n)，主要来自排序操作。

二、通过等量移除操作求字符串最小长度

题意：给定一个只包含两种字母（如 ‘a’ 和 ‘b’）的字符串，每次可以移除两个相邻且不同的字母，求经过任意次操作后字符串的最小长度。

思路：栈模拟

核心观察：移除操作相当于匹配相邻的不同字符对，类似于括号匹配问题。

算法步骤：

1. 初始化一个空栈
2. 遍历字符串中的每个字符：
   • 如果栈不为空且栈顶字符与当前字符不同，则弹出栈顶（表示成功移除一对）
   • 否则将当前字符压入栈中
3. 遍历结束后，栈中剩余字符即为无法移除的部分
4. 栈的大小就是最终字符串的最小长度

示例分析：对于字符串 “abba”：

• 处理 ‘a’：栈为空 → 压入 ‘a’，栈：['a']
• 处理 ‘b’：栈顶 ‘a’ ≠ ‘b’ → 弹出 ‘a’，栈：[]
• 处理 ‘b’：栈为空 → 压入 ‘b’，栈：['b']
• 处理 ‘a’：栈顶 ‘b’ ≠ ‘a’ → 弹出 ‘b’，栈：[]
• 最终栈为空，最小长度为 0

时间复杂度：O(n)，空间复杂度：O(n)

三、统计移除零后不同整数的数目

题意：给定整数 n，问 [1, n] 范围内所有数字移除十进制中的 0 后，得到的不同整数的个数。

思路：数位动态规划

问题分析：移除数字中的 0 后，不同数字可能会映射到同一个结果。例如：105 → 15，150 → 15，1500 → 15。

设数字 n 的位数为 m：

• 位数小于 m 的数字：可以直接计算，位数为 k 的答案数为 9^k（因为每位不能为0，有9种选择）
• 位数等于 m 的数字：需要使用数位DP来精确统计

数位DP状态定义：

dp(i) 表示处理到第 i 位时，前 i 位与 n 的前 i 位完全匹配的情况下，后续能产生的不同整数个数

状态转移过程：

对于第 i 位（从高位到低位）：

1. 选择小于当前位的数字：如果选择数字 j（j < n[i] 且 j ≠ 0），那么后面 m-i-1 位可以任意选择（但不能为0），贡献为 (j-1) * 9^(m-i-1)
2. 选择等于当前位的数字：如果选择 j = n[i] 且 j ≠ 0，则需要继续处理下一位，贡献为 dp(i+1)

状态转移方程：

dp(i) = Σ(j从1到n[i]-1) 9^(m-i-1)  // 当n[i] ≠ 0时
dp(i) = dp(i+1)  // 当n[i] = 0时，直接结束

边界条件：当 i == m 时（处理完所有位），返回 1

最终答案：总答案 = (所有位数小于m的数字个数) + dp(0)

四、统计稳定子数组的数目

题意：给定一个数组和多个区间查询，问每个区间内有多少个连续子数组是严格递增的。

思路1：前缀和 + 边界修正（推荐解法）

核心思想：利用前缀和快速计算区间内的递增子数组总数，然后修正边界处的重复计算问题。

预处理阶段：

1. 定义 dp[i] 表示以位置 i 结尾的递增子数组个数：

   • 如果 arr[i] > arr[i-1]，则 dp[i] = dp[i-1] + 1（可以扩展前面的递增序列）
   • 否则 dp[i] = 1（只能以当前元素单独作为子数组）

2. 计算前缀和数组 pre[i] = pre[i-1] + dp[i]

查询处理：

对于查询区间 [l, r]，初步答案为 pre[r] - pre[l-1]

边界修正（关键步骤）：

如果 arr[l] > arr[l-1]，说明以 l 开头的子数组可能跨越了查询边界，需要减去多算的部分：

• 找到包含 l 的最大递增区间 [x, y]（x ≤ l ≤ y）
• 多算的部分为：(l - x) × (y - l + 1)

优点：实现简单，时间复杂度 O(n + q)

思路2：前缀和 + 分段处理（更清晰的实现）

将区间 [l, r] 自然地分为两部分：

1. [l, m]：从 l 开始到第一个不满足 arr[i] > arr[i-1] 的位置
2. [m+1, r]：剩余部分

分别计算两部分的答案：

• 第一部分：使用等差数列求和公式
• 第二部分：使用前缀和直接计算

优点：逻辑更清晰，避免复杂的边界修正

思路3：高级线段树（过度设计）

节点结构复杂：

struct Node {
  ll sumVal;                    // 区间内递增子数组总数
  pair<ll, int> leftNumVal;     // 左边界信息：<连续递增长度, 末尾值>
  pair<ll, int> rightNumVal;    // 右边界信息：<连续递增长度, 起始值>
  ll len;                       // 区间长度
};

合并策略复杂（需要处理5种情况）：

1. 左右区间连接处不满足递增
2. 整个合并区间都满足递增
3. 左区间全递增，右区间部分递增
4. 右区间全递增，左区间部分递增
5. 连接处满足递增但区间不完全递增

缺点：实现复杂，调试困难，在竞赛中不实用

思路4：莫队算法（离线查询）

适用于查询次数多但可以离线的场景，时间复杂度 O((n + q) × √n)。

对比总结：

• 前缀和解法：简单高效，竞赛首选
• 高级线段树：过度设计，实现复杂
• 莫队算法：适合特定场景，通用性较差

五、总结与反思

这次比赛前三题在12分钟内顺利完成，但第四题的解题过程暴露了一个重要问题：问题想复杂了。

经验教训：

1. 简单优先原则：遇到问题时，首先考虑最直接的解法，不要过度设计
2. 竞赛思维：在限时比赛中，实现速度和代码简洁性比算法”高级度”更重要
3. 问题分析：深入理解问题本质，避免被表面特征误导
4. 工具选择：根据具体场景选择合适的算法工具，不要”杀鸡用牛刀”

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号： tiankonguse
公众号 ID： tiankonguse-code