解决思路
设 \([a_l, a_r]\) 满足要求，而加入 \(a_{r+1}\) 则不满足要求，那么根据题目中相邻两数差不超过 1，\(a_{r+1} - min([a_l, a_r]) = 2\quad or\quad max([a_l, a_r]) - a_{r+1}\) 成立。当有多个 \(a_i = (min([a_l, a_r])\quad or\quad max([a_l, a_r]))\) 时，取最右边的，过程如下图所示
那么，我们只需用 map 来记录每个数字最后出现的为止即可，代码如下
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n; std::cin >> n;
std::vector<int> vec(n, 0);
for (int i = 0; i < n; ++i) std::cin >> vec[i];
std::map<int, int> m;
int cnt, ans; cnt = ans = 0;
for (int i = 0; i < n; ++i) {
int minV = vec[i] - 2;
int maxV = vec[i] + 2;
if (m.find(maxV) != m.end()) {
cnt = i - m[maxV] - 1;
m.erase(maxV);
}
if (m.find(minV) != m.end()) {
cnt = std::min(cnt, i - m[minV] - 1);
m.erase(minV);
}
m[vec[i]] = i;
++cnt;
ans = std::max(ans, cnt);
}
std::cout << ans << "\n";
return 0;
}
误区
- \(cnt\) 应取大-小和小-大中的最小值
- 需要将 \(a_l\) 的值从 map 中删除，因为 \(a_l\) 必定是加入 \(a_{r+1}\) 后的子数组中最大的值或最小的值，不满足新数组的要求，因此应删除该值