Welcome to Subscribe On Youtube
3009. Maximum Number of Intersections on the Chart
Description
There is a line chart consisting of n
points connected by line segments. You are given a 1indexed integer array y
. The k^{th}
point has coordinates (k, y[k])
. There are no horizontal lines; that is, no two consecutive points have the same ycoordinate.
We can draw an infinitely long horizontal line. Return the maximum number of points of intersection of the line with the chart.
Example 1:
Input: y = [1,2,1,2,1,3,2] Output: 5 Explanation: As you can see in the image above, the line y = 1.5 has 5 intersections with the chart (in red crosses). You can also see the line y = 2 which intersects the chart in 4 points (in red crosses). It can be shown that there is no horizontal line intersecting the chart at more than 5 points. So the answer would be 5.
Example 2:
Input: y = [2,1,3,4,5] Output: 2 Explanation: As you can see in the image above, the line y = 1.5 has 2 intersections with the chart (in red crosses). You can also see the line y = 2 which intersects the chart in 2 points (in red crosses). It can be shown that there is no horizontal line intersecting the chart at more than 2 points. So the answer would be 2.
Constraints:
2 <= y.length <= 10^{5}
1 <= y[i] <= 10^{9}
y[i] != y[i + 1]
fori
in range[1, n  1]
Solutions
Solution 1

class Solution { public int maxIntersectionCount(int[] y) { final int n = y.length; int ans = 0; int intersectionCount = 0; TreeMap<Integer, Integer> line = new TreeMap<>(); for (int i = 1; i < n; ++i) { final int start = 2 * y[i  1]; final int end = 2 * y[i] + (i == n  1 ? 0 : y[i] > y[i  1] ? 1 : 1); line.merge(Math.min(start, end), 1, Integer::sum); line.merge(Math.max(start, end) + 1, 1, Integer::sum); } for (final int count : line.values()) { intersectionCount += count; ans = Math.max(ans, intersectionCount); } return ans; } }