136. Widest Water Tank
A builder is laying out vertical boards along a straight line, one unit apart. The array heights gives the height of each board, and the board at index i stands at horizontal position i.
Choose two different boards and use them as the left and right walls of an open-topped tank. The tank holds water up to the height of the shorter wall, and its width is the distance between the two boards, so its capacity is min(heights[i], heights[j]) * (j - i). Boards between the walls are ignored and do not affect the capacity. Return the largest capacity that any pair of boards can give.
Example 1
- Input:
- heights = [3,9,2,7,4]
- Output:
- 14
- Explanation:
Boards at index 1 and 3 (heights 9 and 7) give min(9,7)*2=14. Boards 0 and 4 give min(3,4)*4=12. No pair beats 14.
Example 2
- Input:
- heights = [5,5]
- Output:
- 5
- Explanation:
Only one pair exists, giving min(5,5)*1=5.
Example 3
- Input:
- heights = [0,0,8]
- Output:
- 0
- Explanation:
Every pair contains a board of height 0, so every tank holds nothing and the answer is 0.
Constraints
2 ≤ heights.length ≤ 105
0 ≤ heights[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)