mediumStackPattern: Monotonic Stack
Maximal Visible Bridge Cost Solution
Problem Statement
You are given an integer array heights representing the heights of a series of buildings. A bridge can be built between two buildings at indices i and j (i < j) if and only if all buildings at indices k, where i < k < j, have a height strictly less than min(heights[i], heights[j]). The cost of a valid bridge between i and j is defined as (heights[i] + heights[j]) * (j - i). Return the maximum cost of any valid bridge that can be constructed. If no valid bridges can be built, return 0.
Examples
Example 1:
Input:heights = [4, 2, 3, 1]
Output:14
Explanation: The maximum bridge cost is obtained by connecting building 0 (height 4) and building 2 (height 3). The intermediate building 1 (height 2) is strictly shorter than min(4, 3) = 3. The cost is (4 + 3) * (2 - 0) = 14.
Example 2:
Input:heights = [6, 1, 2, 1, 5]
Output:44
Explanation: The maximum bridge cost is obtained by connecting building 0 (height 6) and building 4 (height 5). All intermediate buildings [1, 2, 1] at indices 1, 2, and 3 are strictly shorter than min(6, 5) = 5. The cost is (6 + 5) * (4 - 0) = 44.
Constraints
- 2 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^6
Time: O(n) Space: O(n)
Using a monotonic decreasing stack, we can efficiently find the 'next greater' building for each element. By maintaining the stack, we ensure that we only consider pairs that satisfy the visibility condition, achieving O(n) time complexity.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.