先做个假设,列的墙不能是浮空的
首先证明必须得到每个column的所有能放水的格子的信息。能放水的格子,也就是C里面空缺的部分。我们可以设想一下,如果不是C而是E呢?能放水的格子就成了两格。如果是楼层状的呢?所以能放水的格子可能是交错的无限个。比如100高度,奇数高度能放水。因此,我们必须获取每个column里面能放水的格子的信息。
然后第二个问题,我们要如何表示这个信息呢?输入可能这么表示。原本输入是list[int]。每个int表示块状高度。现在块状可能不是连续的,就必须list[(int,int)]。两个int代表从哪到哪是墙。这样我们就能从输入获取形状了
那么获取了形状后如何计算该列的雨水呢?显而易见,如果没有墙,能装的雨水还是老套路,问最高高度=min(左侧最高,右侧最高)。有墙的话,也就是这些list[(int,int)]里面截取低于最高高度的部分求和了
那么我们可以照常左单调,右单调。然后遍历每个列获取列的形状。比如左单调5,右单调8。最高高度等于5。该列形状为[(0,0),(3,4)]。于是得到3-1-0=2的容量,和5-4=1的容量。该列雨水为3
如果有封闭区,或者墙可以浮空。那就很麻烦了。
首先证明必须得到每个column的所有能放水的格子的信息。能放水的格子,也就是C里面空缺的部分。我们可以设想一下,如果不是C而是E呢?能放水的格子就成了两格。如果是楼层状的呢?所以能放水的格子可能是交错的无限个。比如100高度,奇数高度能放水。因此,我们必须获取每个column里面能放水的格子的信息。
然后第二个问题,我们要如何表示这个信息呢?输入可能这么表示。原本输入是list[int]。每个int表示块状高度。现在块状可能不是连续的,就必须list[(int,int)]。两个int代表从哪到哪是墙。这样我们就能从输入获取形状了
那么获取了形状后如何计算该列的雨水呢?显而易见,如果没有墙,能装的雨水还是老套路,问最高高度=min(左侧最高,右侧最高)。有墙的话,也就是这些list[(int,int)]里面截取低于最高高度的部分求和了
那么我们可以照常左单调,右单调。然后遍历每个列获取列的形状。比如左单调5,右单调8。最高高度等于5。该列形状为[(0,0),(3,4)]。于是得到3-1-0=2的容量,和5-4=1的容量。该列雨水为3
如果有封闭区,或者墙可以浮空。那就很麻烦了。