每段建筑物的平均高度

/*
 * Problem: Given an array of building heights, find the average height of each building block.
 * Solution: Use Java Streams to calculate the sum and count, then find the average.
 */
import java.util.Arrays;
public class AverageBuildingHeightStream {
    public static double findAverageHeight(int[] heights) {
        return Arrays.stream(heights).average().orElse(0);
    }
}

The solution uses a line sweep algorithm combined with differential counting. For each building, start and end positions are marked in a 'diff' dictionary where heights are added at the start and subtracted at the end. Another 'cnts' dictionary tracks how many buildings start or end at each point. By iterating over the sorted keys of these dictionaries, we compute the current total height and count of buildings at each position. This allows us to determine the average height for any segment where it remains constant. The result is appended to the list if the average height changes from the previous segment or a new segment starts.

O(k log k)

O(k)