Prison Break
Description
A prisoner is planning to escape from prison!
The prison’s gate consists of horizontal and vertical bars that are spaced one unit apart, so the area of each hole between the bars is 1 x 1.
The prisoner manages to remove certain bars to make some bigger holes. Determine the area of the largest hole in the gate after the bars are removed.
Example
n = 6
m = 6
h = [4]
v = [2]In the images below, the left image depicts the initial prison gate with n = 6 horizontal and m = 6 vertical bars. The area of the biggest hole in the bars is 1 x 1. The right image depicts that same gate after the prisoner removes horizontal bar 4 and vertical bar 2, at which point the area of the biggest hole in the bars becomes 2 x 2 = 4.
这题本质上是计算“连续被移除的横杆段”和“连续被移除的竖杆段”所能形成的最大连通空洞面积。由于每移除一段连续的横杆，会让对应方向的空洞高度增加 1；连续移除 k 根横杆，最终高度就是 k+1，竖杆同理。做法是先对 h 和 v 排序，分别扫描求最长连续区间长度，再计算 (max_horizontal_run + 1) × (max_vertical_run + 1) 即可。样例中移除 h=[4]、v=[2]，最大连续段长度都是 1，所以面积为 2 × 2 = 4。
