Dynamic Vista Score
In urban planning and telecommunications, optimizing the placement of communication towers is crucial for maximizing signal coverage and network efficiency. Consider a scenario where a city's skyline is represented by a sequence of tower heights. We want to identify the tower that offers the most 'dynamic vista' – a measure reflecting the combined impact of taller, unblocked towers it can observe, weighted by their height and distance. This problem challenges you to develop an algorithm that can quantify and find the maximum such vista score, which is vital for strategic planning.
You are tasked with implementing a function maxDynamicVistaScore that takes an array of tower heights and returns the highest Dynamic Vista Score found among all towers. For each tower i, its Dynamic Vista Score is calculated as follows:
j is considered 'visible' from tower i (where j != i) if heights[j] > heights[i] AND all towers k strictly between i and j (i.e., min(i,j) < k < max(i,j)) have heights[k] < heights[i]. In simpler terms, j must be the closest tower to i in its direction (left or right) that is strictly taller than i.j, it contributes heights[j] * (abs(i - j) + 1) to tower i's score. The (abs(i - j) + 1) term represents the 'distance factor', where a distance of 1 means adjacent towers.i is the sum of these contributions from all visible towers j (both to its left and right).Function Signature:
function maxDynamicVistaScore(heights: number[]): number
heights: An array of non-negative integers representing tower heights.heights is empty or contains only one tower, no other towers can be visible, so the maximum score should be 0.heights[j] == heights[i], tower j is NOT visible from i according to the definition (it must be strictly taller).Examples
Example 1
Input:
heights = [3,1,4,2,5]
Output:
18
Note:
Let's calculate the score for each tower:
Example 2
Input:
heights = [5,5,5,5]
Output:
0
Note:
Since no tower is strictly taller than any other tower, no towers are considered visible. Therefore, all scores are 0, and the maximum is 0.
Example 3
Input:
heights = [7,6,5,4,3,2,1,8]
Output:
70
Note:
For each tower, we find its closest strictly taller tower to the left and right. For instance:
Constraints
0 <= heights.length <= 10^50 <= heights[i] <= 10^9O(N) time complexity, where N is the number of towers.O(N) space complexity.heights will always be an array of numbers).O(N) solution.O(N) time and O(N) space complexity.Loading editor...