如果您已知道数组元素的限制
(否则请参见下面的更新),我可以向您推荐具有时间复杂度
O(n*log(MaxN))
和空间复杂度O(MaxN)的算法,其中MaxN = Max(V[i])。对于这个算法,我们需要一个结构,它可以在1到N之间以时间复杂度O(log(N))获取数组中的最小值,并以时间复杂度O(log(N))更新数组元素。
Fenwick tree可以完成这些技巧。让我们把这个结构称为
最小化器。然后我们需要做以下几件事情:
- 按给定顺序v[i]迭代所有元素,并将值i放在minimizator的v[i]位置。
- 对于每个元素v[i],在v[i-1]和1之间使用minimizator找到最小值(这是小于v[i]的元素的最小索引)
- 记住i和找到的小于v[i]的元素的最小索引之间的最大差异。
好的。我尝试写一些伪代码:
prepare array (map values)
init minimizator
ansI = -1
ansJ = -1
for i from 0 to v.length-1
minIndexOfElementLessThanCurrent = get min value from 1 to v[i]-1 (inclusive) using minimizator
set to minimizator v[i] position value i
if minIndexOfElementLessThanCurrent is exists
if ansJ - ansI < i - minIndexOfElementLessThanCurrent
ansJ = i
ansI = minIndexOfElementLessThanCurrent
C++ 实现:
class FenwickTree
{
vector<int> t;
int n;
public:
static const int INF = 1000*1000*1000;
void Init (int n)
{
this->n = n;
t.assign (n, INF);
}
int GetMin (int i)
{
int res = INF;
for (; i >= 0; i = (i & (i+1)) - 1)
res = min (res, t[i]);
return res;
}
void Update (int i, int value)
{
for (; i < n; i = (i | (i+1)))
t[i] = min (t[i], value);
}
};
pair<int, int> Solve(const vector<int>& v)
{
int maxElement = 0;
for(int i = 0; i < v.size(); i++)
maxElement = max(maxElement, v[i]);
FenwickTree minimizator;
minimizator.Init(maxElement+1);
int ansI = -1, ansJ = -1;
for(int i = 0; i < v.size(); i++)
{
int minLeftIndex = minimizator.GetMin(v[i]-1);
minimizator.Update(v[i], i);
if(minLeftIndex == FenwickTree::INF) continue;
if(ansJ - ansI < i - minLeftIndex)
{
ansJ = i;
ansI = minLeftIndex;
}
}
return make_pair(ansI, ansJ);
}
更新:
如果元素类型不是整数(例如双精度浮点数),或者数组元素的最大值太大(例如10^9),我们可以将数组值映射到整数集1..N中(它不会影响结果),然后时间复杂度应为O(n * log(n))。
如果元素是整数,就有一个O(max(maxN, n))的解法。因此,如果maxN <= n,则复杂度为O(N)。我们只需要在常数时间O(1)内回答查询“从1到N获取最小值”即可:
1. 创建大小为maxN的数组。
2. 数组的第m[i]个元素是源数组V中值为i的最小索引。
3. 使用动态规划创建相同大小的数组,其中数组元素r[i]是 1<=j<=i 的 m[j] 的最小值。递推式为 r[i] = min(r[i-1], m[i])。
这个算法的主要思想与上面相同,只是使用数组
r
来找到从
1
到
v[i]
的最小值。
C++ implementation:
pair<int, int> Solve(const vector<int>& v)
{
int maxElement = 0;
for(int i = 0; i < v.size(); i++)
maxElement = max(maxElement, v[i]);
vector<int> minimum(maxElement + 1, v.size() + 1);
for(int i = 0; i < v.size(); i++)
minimum[v[i]] = min(minimum[v[i]], i);
for(int i = 1; i < minimum.size(); i++)
minimum[i] = min(minimum[i-1], minimum[i]);
int ansI = -1, ansJ = -1;
for(int i = 0; i < v.size(); i++)
{
int minLeftIndex = minimum[v[i]-1];
if(minLeftIndex >= i) continue;
if(ansJ - ansI < i - minLeftIndex)
{
ansJ = i;
ansI = minLeftIndex;
}
}
return make_pair(ansI, ansJ);
}
如果元素是双倍的,或者是其他的(非常大的整数),我们无法在线性时间内将元素映射到集合1..N中(或者可以吗?)。我只知道一个O(n*log(n))的解决方案(排序元素等)。
j-i
的一个好的下限。首先,找到两个连续的升序条目。然后,从数组末尾开始向前查找大于较低条目的条目。接着,从较低条目开始向前查找小于上限条目的条目。 - Neil