题目描述
一个长度为 n
下标从 0 开始的整数数组 arr
的 不平衡数字 定义为,在 sarr = sorted(arr)
数组中,满足以下条件的下标数目:
0 <= i < n - 1
,和sarr[i+1] - sarr[i] > 1
这里,sorted(arr)
表示将数组 arr
排序后得到的数组。
给你一个下标从 0 开始的整数数组 nums
,请你返回它所有 子数组 的 不平衡数字 之和。
子数组指的是一个数组中连续一段 非空 的元素序列。
样例
输入:nums = [2,3,1,4]
输出:3
解释:总共有 3 个子数组有非 0 不平衡数字:
- 子数组 [3, 1],不平衡数字为 1。
- 子数组 [3, 1, 4],不平衡数字为 1。
- 子数组 [1, 4],不平衡数字为 1。
其他所有子数组的不平衡数字都是 0,所以所有子数组的不平衡数字之和为 3。
输入:nums = [1,3,3,3,5]
输出:8
解释:总共有 7 个子数组有非 0 不平衡数字:
- 子数组 [1, 3],不平衡数字为 1。
- 子数组 [1, 3, 3],不平衡数字为 1。
- 子数组 [1, 3, 3, 3],不平衡数字为 1。
- 子数组 [1, 3, 3, 3, 5],不平衡数字为 2。
- 子数组 [3, 3, 3, 5],不平衡数字为 1。
- 子数组 [3, 3, 5],不平衡数字为 1。
- 子数组 [3, 5],不平衡数字为 1。
其他所有子数组的不平衡数字都是 0,所以所有子数组的不平衡数字之和为 8。
限制
1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
算法1
(枚举,有序集合) $O(n^2 \log n)$
- 枚举子数组的起点,对于每个起点,定义有序集合,然后按顺序遍历子数组的终点。
- 定义计数器 $cnt$,表示当前区间内不平衡的数字个数。在遍历终点的过程中,需要不断修改 $cnt$。如果当前数字在有序集合中出现过,则答案直接累加 $cnt$,因为新加入一个重复的数字,和不加入之前的不平衡的总数字个数一样。
- 否则,通过二分在有序集合上找到大于当前数字的最小值的位置 $it$。如果 $it$ 存在(非迭代器终点),且 $it$ 的值大于当前数字加 $1$,则需要增加一个不平衡数。
- 如果有续集不为空,且上一步中的 $it$ 不是迭代器起点,则定义 $upper$ 为 $it$ 的值(如果 $it$ 为终点,则令 $upper$ 为 $0$)。此时向前移动 $it$,找到小于当前数字的最大值的位置 $new_it$。
- 如果 $newit$ 的值加 $1$ 小于 $upper$,则说明之前 $new_it$ 的值和 $upper$ 之间是产生过一个不平衡数的,但由于他们中间新插入了数字,则这个不平衡数就不再计算了,需要减少一个不平衡数。
- 如果 $newit$ 的值加 $1$ 小于当前数字,则再加回这个不平衡数。
- 最后当前数字插入到有序集中,并让答案累加 $cnt$。
时间复杂度
- 枚举起点的时间复杂度为 $O(n)$,每个起点都需要遍历 $O(n)$ 个终点,遍历每个终点都需要 $O(\log n)$ 的时间操作有序集,故总时间复杂度为 $O(n^2 \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储有序集。
C++ 代码
class Solution {
public:
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
for (int i = 0; i < n; i++) {
set<int> s;
int cnt = 0;
for (int j = i; j < n; j++) {
if (s.find(nums[j]) != s.end()) {
ans += cnt;
continue;
}
auto it = s.upper_bound(nums[j]);
if (it != s.end() && nums[j] + 1 < *it)
++cnt;
if (!s.empty() && it != s.begin()) {
int upper = (it == s.end() ? 0 : *it);
--it;
if (*it + 1 < upper)
--cnt;
if (*it + 1 < nums[j])
++cnt;
}
s.insert(nums[j]);
ans += cnt;
}
}
return ans;
}
};
算法2
(枚举,哈希表) $O(n^2)$
- 在算法 1 的基础上,使用哈希表每次考察当前数字 $x$ 的 $x+1$ 与 $x-1$ 是否存在。
- 对于每个终点,默认给当前元素增加一个不平衡数,如果发现 $x+1$ 或 $x-1$ 存在,都需要减去一个不平衡数。
- 注意,这是枚举终点时,需要从起点的下一个位置开始,且需要特殊处理起点位置的值,提前插入哈希表。
时间复杂度
- 枚举起点的时间复杂度为 $O(n)$,每个起点都需要遍历 $O(n)$ 个终点,遍历每个终点仅需要常数的时间,故总时间复杂度为 $O(n^2)$。
- 如果使用数组存储哈希表,则时间复杂度为 $O(n(n + m))$,因为需要 $O(m)$ 的时间初始化哈希表,其中 $m$ 为最大的数字范围。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
- 如果使用数组存储哈希表,则额外空间为 $O(m)$。
C++ 代码
class Solution {
public:
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
unordered_set<int> seen;
int ans = 0;
for (int i = 0; i < n; i++) {
seen.clear();
seen.insert(nums[i]);
int cnt = 0;
for (int j = i + 1; j < n; j++) {
if (seen.find(nums[j]) != seen.end()) {
ans += cnt;
continue;
}
++cnt;
if (seen.find(nums[j] + 1) != seen.end()) --cnt;
if (seen.find(nums[j] - 1) != seen.end()) --cnt;
ans += cnt;
seen.insert(nums[j]);
}
}
return ans;
}
};
C++ 代码(使用数组存储哈希表)
const int N = 1010;
class Solution {
private:
bool seen[N];
public:
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
for (int i = 0; i < n; i++) {
memset(seen, false, sizeof(seen));
seen[nums[i]] = true;
int cnt = 0;
for (int j = i + 1; j < n; j++) {
if (seen[nums[j]]) {
ans += cnt;
continue;
}
++cnt;
if (seen[nums[j] + 1]) --cnt;
if (seen[nums[j] - 1]) --cnt;
ans += cnt;
seen[nums[j]] = true;
}
}
return ans;
}
};
算法3
(计算贡献,思维题,数学) $O(n^2)$
- 对于每个位置,计算其作为某个子数组中的元素时所产生的贡献,显然每个位置的计算都是独立的。
- 为了不重复不遗留的计算,我们只考虑每个数字 $x$ 与子数组中小于等于 $x-2$ 的数字产生的贡献。
- 如果所有数字都不重复,则对于位置 $i$ 的数字 $x$,找到小于 $i$ 的左开右闭区间 $(s1, e1]$,满足 $s1$ 是离 $i$ 最近且值等于 $x-1$ 的位置(如果不存在则为 $-1$),$e1$ 是离 $i$ 最近且值小于 $x$ 的位置(如果不存在则也为 $-1$)。同理,$i$ 的右侧也可以找到类似的左闭右开区间 $[s2, e2)$。此时,可以看出,起点在 $(s1, e1]$ 且终点在 $[i, e2)$,或者起点在 $(s1, i]$ 且终点在 $[s2, e2)$ 的情况下,$x$ 都会和一个小于等于 $x-2$ 的元素产生 $1$ 的贡献。
- 根据乘法原理,通过去掉不合法的方式来避免重复计算,贡献可以写为 $(i - s1)(e2 - i) - (i - e1)(s2 - i)$。
- 接下来想办法处理重复的数字,对于重复的数字,我们只需要规定「计算的方向」,就可以避免重复计算贡献,即左侧区间的定义改为 $s1$ 是离 $i$ 最近且值等于 $x-1$ 或 $x$ 的位置(如果不存在则为 $-1$),$e1$ 是离 $i$ 最近且值小于等于 $x$ 的位置(如果不存在则也为 $-1$),右侧区间的定义改为 $s2$ 是离 $i$ 最近且值小于 $x$ 的位置(如果不存在则为 $n$),$e2$ 是离 $i$ 最近且值等于 $x-1$ 的位置(如果不存在则也为 $n$)。
时间复杂度
- 计算每个位置的贡献的时间为 $O(n)$,故总时间复杂度为 $O(n^2)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
for (int i = 0; i < n; i++) {
int prev = 0;
int e1 = i - 1;
while (e1 >= 0 && nums[e1] > nums[i])
--e1;
int s1 = e1;
while (s1 >= 0 && (nums[s1] > nums[i] || nums[s1] < nums[i] - 1))
--s1;
int s2 = i + 1;
while (s2 < n && nums[s2] >= nums[i])
++s2;
int e2 = s2;
while (e2 < n && (nums[e2] >= nums[i] || nums[e2] < nums[i] - 1))
++e2;
ans += (i - s1) * (e2 - i) - (i - e1) * (s2 - i);
}
return ans;
}
};
算法4
(计算贡献,思维题,数学,单调栈) $O(n)$
- 根据算法 3 的思路,注意到可以使用单调栈,在线性时间内求出每个位置的 $e1$ 和 $s2$ 值。
- 而每个位置的 $s1$ 和 $e2$ 值,可以分别通过正序遍历和逆序遍历配合哈希表求出。
- 最终通过遍历所有位置的贡献,累加求和。
时间复杂度
- 单调栈的时间复杂度为 $O(n)$,计算 $s1$ 和 $e2$ 的时间复杂度为 $O(n)$,故总时间复杂度为 $O(n)$。
- 如果使用数组存储哈希表,需要 $O(m)$ 的时间预处理哈希表,故时间复杂度为 $O(n + m)$。其中 $m$ 为最大的数字范围。
空间复杂度
- 需要 $O(n)$ 的额外空间存储单调栈和哈希表。
- 如果使用数组存储哈希表,则需要 $O(n + m)$ 的额外空间。
C++ 代码
class Solution {
public:
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
stack<int> st;
vector<int> e1(n, -1), s2(n, n);
for (int i = 0; i <= n; i++) {
while (!st.empty() && (i == n || nums[i] < nums[st.top()])) {
int t = st.top();
st.pop();
s2[t] = i;
if (!st.empty())
e1[t] = st.top();
}
st.push(i);
}
unordered_map<int, int> prev, suff;
vector<int> s1(n, -1), e2(n, n);
for (int i = 0; i < n; i++) {
if (prev.find(nums[i]) != prev.end())
s1[i] = max(s1[i], prev[nums[i]]);
if (prev.find(nums[i] - 1) != prev.end())
s1[i] = max(s1[i], prev[nums[i] - 1]);
prev[nums[i]] = i;
}
for (int i = n - 1; i >= 0; i--) {
if (suff.find(nums[i] - 1) != suff.end())
e2[i] = min(e2[i], suff[nums[i] - 1]);
suff[nums[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += (i - s1[i]) * (e2[i] - i) - (i - e1[i]) * (s2[i] - i);
return ans;
}
};
C++ 代码(使用数组存储哈希表)
const int N = 1010;
class Solution {
private:
int prev[N], suff[N];
public:
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
stack<int> st;
vector<int> e1(n, -1), s2(n, n);
for (int i = 0; i <= n; i++) {
while (!st.empty() && (i == n || nums[i] < nums[st.top()])) {
int t = st.top();
st.pop();
s2[t] = i;
if (!st.empty())
e1[t] = st.top();
}
st.push(i);
}
for (int i = 0; i < N; i++) {
prev[i] = -1;
suff[i] = n;
}
vector<int> s1(n), e2(n);
for (int i = 0; i < n; i++) {
s1[i] = max(prev[nums[i]], prev[nums[i] + 1]);
prev[nums[i]] = i;
}
for (int i = n - 1; i >= 0; i--) {
e2[i] = suff[nums[i] + 1];
suff[nums[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += (i - s1[i]) * (e2[i] - i) - (i - e1[i]) * (s2[i] - i);
return ans;
}
};
算法5
(计算贡献,哈希表) $O(n)$
- 进一步简化算法 3 的计算方式,可以发现,如果找到了当前数字 $x$ 的位置 $i$ 左侧最近的 $x$ 或者 $x-1$,记为 $l_i$,以及右侧最近的 $x-1$,记为 $r_i$,则当前位置 $i$ 贡献的答案可以写为 $(i - l_i)(r_i - i)$,但这里其实包含了非法贡献,即 $i$ 作为子数组最小值时产生。
- 为了去掉非法贡献,对所有位置都计算为贡献后,统一减去每个值作为最小值时的子数组个数,也就是所有的子数组都会被额外多计算一次贡献,所以减去 $n(n+1)/2$。
时间复杂度
- 使用哈希表,正序和倒序遍历,分别得到 $l_i$ 和 $r_i$。
- 计算答案的时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
unordered_map<int, int> prev, suff;
vector<int> l(n, -1), r(n, n);
for (int i = 0; i < n; i++) {
if (prev.find(nums[i]) != prev.end())
l[i] = max(l[i], prev[nums[i]]);
if (prev.find(nums[i] - 1) != prev.end())
l[i] = max(l[i], prev[nums[i] - 1]);
prev[nums[i]] = i;
}
for (int i = n - 1; i >= 0; i--) {
if (suff.find(nums[i] - 1) != suff.end())
r[i] = min(r[i], suff[nums[i] - 1]);
suff[nums[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += (i - l[i]) * (r[i] - i);
return ans - n * (n + 1) / 2;
}
};
很强Orz