给定两个长度相等的数组n为正整数值的a和b，我想要一个算法来找到(a[j] - a[i]) * min(b[j], b[i])的最大数量，使得0 <= i < j < n。这个问题在某种程度上与两个元素之间的最大差有关，使得较大的元素出现在较小的数字之后，但它也引入了对数组b的新限制。由于min()的限制，该算法不能通过创建新的数组c来使用，从而对于每个i:c[i] = a[i] * b[i]。所以我想知道这个问题是否可以在线性O(n)或O(n*logn)中求解，或者它是否可以证明仅在O(n^2)中是可解的。任何提示都很好。
对于固定的j，我们对i < j有两种情况：
1.b[i] < b[j]
我们必须找到最小a[i]，这样这个条件成立。
我们可以使用一个deque数据结构d1，其中a[d1.front]将始终是这个最小值-所以我们对d1进行排序，使条件成立，并且它包含a中的最小值。注意，d1只包含位置，不包含值。
对于每个j(您可能需要对d1在您选择的语言中是否为空进行一些健全性检查(：
while a[j] <= a[d1.back]:
d.pop_back()
while b[d1.front] >= b[j]:
d.pop_front()
quantity1 = (a[j] - a[d1.front]) * b[d1.front]
d1.push_back(j)
2.b[i] >= b[j]
对d2执行相同的操作来计算quantity2。然后，取两个Q的最大值，并将该最大值与全局最大值进行比较
这可能看起来像O(n^2)，因为您仍然会有嵌套的循环，但它是O(n)：请注意，每个值最多会进入和离开每个deque一次。