leetcode 周赛 472，排名 78

零、背景

这次比赛第四题比较难，我想到线段树维护集合的第一个点，也发现前缀和满足整数连续性，但不知道如何求第一个指定值。

A: 遍历
B: 枚举 + 前缀统计
C: DFS + 贪心
D: 二分 + 线段树

排名：78 代码地址： https://github.com/tiankonguse/leetcode-solutions

一、缺失的最小倍数

题意：给一个数组，问 k 的所有倍数中，最小的未出现的数字是多少。

思路：

经典的问题，按最小的未出现的数字来理解就可以了。

方法 1：排序 + 遍历

从小到大遍历数字，判断是否是 k 的倍数；如果是，再判断是否连续；若连续，则更新已找到的最大值。

方法 2：统计 + 遍历

使用哈希表统计所有 k 的倍数，然后从小到大枚举所有的 k 的倍数，遇到不存在的就停止。

二、最长平衡子数组 I

题意：给一个数组，求一个最长的子数组，使得子数组中不同偶数的个数与不同奇数的个数相等。

思路：暴力枚举

数据范围 1500，可以用双层循环暴力枚举所有子数组来判断是否满足要求。

数据结构：两个哈希表 判断：两个哈希表大小是否相等

三、大于 target 的最小字典序排列

题意：给两个字符串 A 和 B，求 A 的一个字典序大于 B 的最小的排列。

思路：DFS 贪心

由于要字典序最小，显然相等的前缀需要尽可能的长。
一旦遇到某个位置不相等，则显然需要在剩余字符中，选择大于当前位置的最小字符。
最后，剩余的字符按升序排列。

按这个思路来看，存在一个 bad case。 第二步如果不存在大于当前位置的字符该怎么办？
显然，需要回退，上一个位置去找大于上一个位置的最小字符。

这个过程是递归的，有可能连续几个位置都没找到。
所以写成递归比较好理解。

bool Dfs(int i) {
  if (i == n) return false;  // 说明全部相等
  const char c = target[i];
  if (H.count(c)) { // 相等，尝试匹配下个位置
    H[c]--;
    if (H[c] == 0) H.erase(c);
    ans.push_back(c);
    if (Dfs(i + 1)) return true;
    H[c]++;
    ans.pop_back();
  }
  auto it = H.upper_bound(c);
  if (it == H.end()) return false; // 不存在大于当前位置的字符
  ans.push_back(it->first);
  H[it->first]--;
  if (H[it->first] == 0) H.erase(it->first);
  for (auto& p : H) {
    ans.append(string(p.second, p.first));
  }
  return true; // 找到答案
}

四、最长平衡子数组 II

题意：与第二题一样，但数据范围变大了很多。

数据范围：1e5。

基本思路：显然，不能再用暴力两层循环了。
所以，当遍历到位置 R 时，我们需要在所有以 R 结尾的子数组中，找到最长的不同奇偶数个数相等的那个。

数字去重，就是集合，但是集合不满足加减法定律：即一个前缀的集合大小为 A，另一个前缀的集合大小为 B，两个前缀求差，区间内的集合大小不是 A-B。
这是因为存在一些元素即在第二个前缀里（小前缀），也在区间内（大前缀减小前缀）。

针对这个问题，一种经典的做法是去重。
由于我们是求所有以 R 结尾的子数组的答案，所以只需要保留目前为止最后一个出现的位置。

又由于已经去重，目标是统计奇数和偶数的个数，所以奇数标记为 1，偶数标记为 -1，重复删除的位置标记为 0。

const int x = a[i - 1];
const int v = (x & 1) ? 1 : -1;

此时，问题就转化为：在所有以 R 结尾的子数组中，求子数组和为 0 的最长长度。
这时候就可以使用前缀和来优化，即寻找第一个前缀和与当前位置的前缀和相等的位置。

如何维护这个前缀和呢？
加入一个新数字，前缀和就是自身，前面的前缀和都不变。
加入一个重复数字，需要先删除前面的数字，此时会影响一个区间的前缀和，故该区间的前缀和都需要更新。
故，我们维护一个前缀和的线段树即可。

if (lastPos.count(x)) {
  segTree.Update(lastPos[x], i - 1, -v); // 区间前缀和去除之前的贡献
  sum -= v;
}
lastPos[x] = i;
sum += v;
segTree.Update(i, i, sum); // 单点写入当前位置的前缀和

线段树有了，如何查找目标数字的第一个位置呢？

这时候就需要利用上前缀和的一个性质了。
由于每个位置的值只可能是 [-1, 0, 1]，故可以推导出前缀和这个函数曲线是连续的。
故，维护一个区间最大值和最小值，即可判断区间内是否有指定数字了。

此时，通过二分，即可找到第一个位置。

if (sum == 0) { // 特殊判断：整个区间都是答案
  ans = max(ans, i);
  continue;
}
int l = 1, r = i;  // i 肯定是答案
while (l < r) {
  const int mid = (l + r) >> 1;
  auto [minVal, minPos] = segTree.QueryMin(1, mid);
  auto [maxVal, maxPos] = segTree.QueryMax(1, mid);
  if (minVal <= sum && sum <= maxVal) {
    r = mid;
  } else {
    l = mid + 1;
  }
}
ans = max(ans, i - r);

五、最后

赛后想了想，最后一道题的逻辑链路比较长，再给我 10 分钟，应该就可以做出来了。
我想到了前缀集合大小不支持相减，也想到了线段树维护集合的第一个点，也发现前缀和满足整数连续性，但没想到怎么求第一个指定值。
这次做了这道题后，以后应该就会做了。

这个题型总结一下就是有一个连续序列函数，求第一个解。
通过维护前缀的最大值和最小值，即可判断前缀是否有解，从而二分找到答案。

《完》

-EOF-

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