Skip to content

2866.beautiful-towers-ii.md

Latest commit

 

History

History
97 lines (76 loc) · 2.46 KB

2866.beautiful-towers-ii.md

File metadata and controls

97 lines (76 loc) · 2.46 KB

2866. Beautiful Towers II

Clarification Questions

  • No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output:

Edge / Corner Cases

Input: 
Output:

Idea!! We iterate i from left to right and use i as peak to build the highest tower subject to the max height from left to i (peak).

// Index
0, 1, 2, 3, 4
         i -> use it as peak
         /
       / |
      /  |
   /  |  |
/  |  |  |
|  |  |  |  |

We calculate from left to right first and then from right to left. Then we sum up the two sums and return the maximum among the sums. That is overall idea of this problem.

How can we calculate the height sum from left to right? Suppose we have increasing height at the beginning, we can build the tower with that height directly, so we just sum up the height as answer.

[1, 4, 6, ...] sum
 1,              1
 1, 4            5
 1, 4, 6        11

       ▩
       ▩
    ▩  ▩
    ▩  ▩
    ▩  ▩
 ▩  ▩  ▩

Then we encounter a lower height, what should we do?

[1, 4, 6, 3, ....]
          ^
       ▩
       ▩
    ▩  ▩  
    ▩  ▩  ▩
    ▩  ▩  ▩
 ▩  ▩  ▩  ▩

We should destroy all the previous towers which are higher than the current one (4 and 6), and rebuild for them with current height (3), plus build for the current tower:

[1, 4, 6, 3, ....] sum
          ^

    ▩  ▩  ▩          
    ▩  ▩  ▩
 ▩  ▩  ▩  ▩  
 1  3  3  3         10

What if we have another lower height next? Then we should destroy all the tower which is higher than the current tower (height is 1) and rebuild for all the tower we have destroyed before and current tower with height 1:

[1, 4, 6, 3, 1, ...] sum
             ^

    ▩  ▩  ▩          
    ▩  ▩  ▩
 ▩  ▩  ▩  ▩  ▩  

// Destroy all the tower which is higher than the current tower (height is 1) and rebuild with height 1:

 ▩  ▩  ▩  ▩  ▩
 1  1  1  1  1         5

For this idea, we can use increasing monotonic stack to build the solution:

  • If the height is increasing, we just sum up the height and push into the stack.
  • If the height is decreasing, we have to destroy all the previous towers, then rebuild the previously destroyed towers + current tower with the current height.

We do the same thing from right to left. Sum up the two results and minus the double counting.