Oracle's Skyline Influence Sum
In Oracle's urban planning division, we're analyzing the "influence" of buildings on their surroundings. For a given row of buildings, each with a specific height, we need to quantify the cumulative "influence" exerted by shorter buildings to its left. This metric helps us understand visual impact and potential development constraints.
You are tasked with implementing a function calculateInfluenceSums that takes an array of building heights and returns an array where each element result[i] represents the "influence score" for the building at index i.
The "influence score" for a building at index i is defined as follows:
result[i] is the sum of heights[j] for all j < i such that heights[j] is strictly shorter than heights[i], AND heights[j] is either the nearest strictly shorter building to heights[i] on its left, or it's the nearest strictly shorter building to another building heights[k] (where j < k < i) that itself contributes to heights[i]'s influence score. This forms a chain of shorter buildings leading up to heights[i].
More precisely, let prevSmaller[idx] be the index of the nearest building to the left of idx that has a strictly smaller height. If no such building exists, prevSmaller[idx] is -1.
Then, result[i] can be recursively defined:
prevSmaller[i] is -1, then result[i] = 0.result[i] = heights[prevSmaller[i]] + result[prevSmaller[i]].Function Signature:
function calculateInfluenceSums(heights: number[]): number[]
heights: An array of integers representing the heights of buildings. heights[i] is the height of the i-th building.result, where result[i] is the influence score for the building at index i, as defined above.heights is empty, return an empty array.heights contains only one building, its influence score is 0.heights can contain up to 10^5 elements. Your solution should be efficient enough to handle this scale.Examples
Example 1
Input:
heights = [3, 1, 4, 2, 5]
Output:
[0, 0, 1, 1, 3]
Note:
heights[0]=3: No buildings to the left. Score = 0.heights[1]=1: No buildings to the left are strictly shorter. Score = 0.heights[2]=4: prevSmaller[2] is index 1 (heights[1]=1). Score = heights[1] + result[1] = 1 + 0 = 1.heights[3]=2: prevSmaller[3] is index 1 (heights[1]=1). Score = heights[1] + result[1] = 1 + 0 = 1.heights[4]=5: prevSmaller[4] is index 3 (heights[3]=2). Score = heights[3] + result[3] = 2 + 1 = 3.Example 2
Input:
heights = [10, 5, 8, 3, 12]
Output:
[0, 0, 5, 0, 3]
Note:
heights[0]=10: Score = 0.heights[1]=5: prevSmaller[1] is -1. Score = 0.heights[2]=8: prevSmaller[2] is index 1 (heights[1]=5). Score = heights[1] + result[1] = 5 + 0 = 5.heights[3]=3: prevSmaller[3] is -1. Score = 0.heights[4]=12: prevSmaller[4] is index 3 (heights[3]=3). Score = heights[3] + result[3] = 3 + 0 = 3.Example 3
Input:
heights = [1, 2, 3, 4, 5]
Output:
[0, 1, 3, 6, 10]
Note:
heights[0]=1: Score = 0.heights[1]=2: prevSmaller[1] is index 0 (heights[0]=1). Score = heights[0] + result[0] = 1 + 0 = 1.heights[2]=3: prevSmaller[2] is index 1 (heights[1]=2). Score = heights[1] + result[1] = 2 + 1 = 3.heights[3]=4: prevSmaller[3] is index 2 (heights[2]=3). Score = heights[2] + result[2] = 3 + 3 = 6.heights[4]=5: prevSmaller[4] is index 3 (heights[3]=4). Score = heights[3] + result[3] = 4 + 6 = 10.Constraints
1 <= heights.length <= 10^50 <= heights[i] <= 10^9number in TypeScript/JavaScript, which handles up to 2^53 - 1).Loading editor...