java - 如何快速找到给出最大值的点？请使用 Java 或 C++ 代码

Question

我需要一种快速的方法来在间隔重叠时找到最大值，与找到重叠最多的点不同，有“顺序”。我会有 int[][] data int[] 中的 2 个值，其中第一个数字是中心，第二个数字是半径，越靠近中心，该点的值就越大。例如，如果我得到如下数据:

int[][] data = new int[][]{
{1, 1},
{3, 3},
{2, 4}};

然后在数轴上，这就是它的样子:

x axis: -2 -1 0 1 2 3 4 5 6 7  
   1 1:       1 2 1  
   3 3:       1 2 3 4 3 2 1  
   2 4:  1  2 3 4 5 4 3 2 1  

因此，为了使我的点的值尽可能大，我需要选择点 x = 2，这给出了 1 + 3 + 5 = 9 的总值，这是最大的可能值。有没有办法快速做到？像 O(n) 或 O(nlogn) 的时间复杂度

Answer 1

这可以通过一个简单的 O(n log n) 算法来完成。
考虑值(value)函数v(x)，然后考虑它的离散导数dv(x)=v(x)-v(x-1)。假设你只有一个区间，比如 {3,3} . dv(x) 是从-无穷大到-1 的0，然后是从0 到3 的1，然后是从4 到6 的-1，然后是从7 到无穷大的0。也就是说，导数在“刚好在”-1 之后变化了 1，刚好在 3 之后变化了 -2，刚好在 6 之后变化了 1。
对于 n 个区间，有 3*n 次导数变化(其中一些可能发生在同一点)。所以找到所有衍生变化的列表(x,change) ，按它们的 x 对它们进行排序，然后迭代整个集合。
看:

intervals = [(1,1), (3,3), (2,4)]

events = []
for mid, width in intervals:
    before_start = mid - width - 1
    at_end = mid + width
    events += [(before_start, 1), (mid, -2), (at_end, 1)]

events.sort()

prev_x = -1000
v = 0
dv = 0

best_v = -1000
best_x = None

for x, change in events:
    dx = x - prev_x
    v += dv * dx
    if v > best_v:
        best_v = v
        best_x = x
    dv += change
    prev_x = x

print best_x, best_v

还有java代码:

 TreeMap<Integer, Integer> ts = new TreeMap<Integer, Integer>();
        
    for(int i = 0;i<cows.size();i++) {
        int index = cows.get(i)[0] - cows.get(i)[1];
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) + 1);
        }else {
            ts.put(index, 1);
        }
            
        index = cows.get(i)[0] + 1;
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) - 2);
        }else {
            ts.put(index, -2);
        }
            
        index = cows.get(i)[0] + cows.get(i)[1] + 2;
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) + 1);
        }else {
                ts.put(index, 1);
        }
    }
        
    int value = 0;
    int best = 0;
    int change = 0;
    int indexBefore = -100000000;
        
    while(ts.size() > 1) {
        int index = ts.firstKey();
        value += (ts.get(index) - indexBefore) * change;
        best = Math.max(value, best);
        change += ts.get(index);
        ts.remove(index);
    }

哪里cows是数据