leetcode 第 440 场算法比赛

背景

这次比赛最后一题看错题了，11:50 才发现正确题意，时间肯定来不及了，没想到做三道题就进入千百名了。

A: 枚举
B: K 大小的堆
C: 二分+线段树
D: 滑动窗口

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

一、将水果放入篮子 II

题意：给 n 个水果，m 个篮子，从左到右依次为水果选择一个合适的篮子，如果有多个，需要是最左边的篮子。
问最后有多少个水果没合适的篮子。

思路：枚举

每个水果遍历所有篮子，找到第一个合适的篮子，打上标记。
如果没找到，答案加 1。

复杂度：O(n*m)

二、选出和最大的 K 个元素

题意：给两个长度相同的数组 num1 和 nums2，对于每个下标 i，所有 nums1[j]<nums1[i]的下标 j 可能有很多个，最多选择 K 个下标，对 nums2[j] 进行求和，目标是和最大。

思路：堆

分析可以发现，两个数组的下标是绑定的，且下标之间没有顺序要求。
故可以对两个数组按 nums1 进行排序。
这样，对于每个下标 i， 假设最大的小于 nums1[i] 的下标是 j， 则 [0,1] 对应的数字都小于 nums1[i]。

我们可以先预处理出每个下标 j 前面所有元素的 TOP K 元素和。
这样，对于每个下标 i，只需要二分查找到下标 j 即可。

排序复杂度：O(n log(n)) 预处理复杂度：O(n log(k))
二分+计算答案复杂度：O(n log(n))

单调性优化： 计算答案时，可以发现 j 是单调递增的。
故可以维护一个双指针来代替二分，从而把计算答案的复杂度降低到 O(n)

综合复杂度：O(n log(n))

三、将水果装入篮子 III

题意：与第一题一样，不过数据范围变大了。

思路：

对于第一个水果，目标是找到最左边的第一个合适的篮子。
这种问题，一般需要拆分为两个子问题：
1）指定区间是否有合适的篮子
2）二分查找缩小区间，找到第一个合适的篮子

指定区间是否有合适的篮子，可以通过线段树的区间最大值来判断。

复杂度：O(n log(n))

四、删除一个冲突对后最大子数组数目

题意：给一个1到n顺序排列的数组，然后给若干个二元素代表这这两个数字不能同时出现。
问恰好删除一个二元组后，可以得到的最多的非空合法子数组数量。

思路：滑动窗口

首先需要读到这道题。
1到n顺序排列的数组指的是数组 1,2,3,...,n。
非空合法子数组，指的是数组中不存在冲突对。

PS：比赛的时候，我读错题了，当做子序列了。

子数组有一个很好的性质：连续性。
如果选择一个子数组 [l,r]，则在 [l,r] 中的任意两个数字，肯定都不存在冲突。
换言之，如果(l,r) 存在冲突，则不可能存在子数组 [L,R]，满足 L<=l && r<=R。

基于这个性质，我们很容易计算出没有删除的子数组数量。

假设以 L 为起始位置，则最多有多少个非空合法子数组呢？
显然，需要找到 L 之后的所有冲突对里面的最小最小 r。
则子数组的数量为 r-L。

这个我们可以逆序预处理，计算出每个位置为起始位置的子数组数量。

接下来，我们来考虑删除一个二元组的情况。
假设删除的二元组是 (l,r)，则原先起始位置为 L，最小边界为 r 的子数组数量，可以变的更多。

具体增加多少个呢？
假设次小边界为 r1，则新的子数组个数为 r1-L，新增 r1-r 个。

通过 r 使得子数组增多的起始位置可能很多，这些位置都会通过 r 增加子数组个数，所以可以都累加起来储存在 r 位置。
这些累加和就是删除二元组(l,r)新增的子数组个数。

最小值和次最小值，可以通过堆来维护。

ll sum = 0;  // 不删除可以得到的最大子数组个数
min_queue<ll> minQue;
vector<ll> secondMinNum(n + 2, 0);
minQue.push(n + 1);  // 至少存在一个边界
minQue.push(n + 1);  // 至少存在一个边界
for (int l = n; l >= 1; l--) {
  for (auto v : groups[l]) {
    minQue.push(v);
  }
  ll r0 = minQue.top();  // [l, r) 最小值
  sum += r0 - l; // 不删除的答案

  minQue.pop();
  ll r1 = minQue.top(); // 次小值
  minQue.push(r0);
  secondMinNum[r0] += r1 - r0; // i位置的最小值删除后新增的答案
}

最后找到新增最多的答案即可。

ll maxAdd = 0;
for (auto v : secondMinNum) {
  maxAdd = max(maxAdd, v);
}
return sum + maxAdd;

优化：可以发现，我们只需要找到次小值，故可以维护一个大小为 2 的堆。

五、最后

这次比赛最后一题读错题了，不过后来想了想，及时没读错题，也不一定做出进来。
不删除冲突还能想出来，但是删除冲突这个，不是很好想，冲突二元组的问题，转化为某个位置为最小值被删除后计算次最小值的问题。
这个转换思维难度比较大，需要多做题来训练。

《完》

-EOF-

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