题意:给定一个只包含BW字符的矩阵。求只包含W的矩阵的个数。

思路:首先我们想想对于一个全是W的矩阵,包含多少个子矩阵呢。我们数子矩阵的原则是 对于某一个点。只数与他相邻的左边和上面的位置。

WW

WW

对于这个矩阵的话。从第一行开始看。对于(0,0)这个W,他包含一个子矩阵,对于(1,0)这个点加上左边的一个。是两个子矩阵。

对于(1,0)这个点。包含是2个。对于(1,1)这个W,包含4个子矩阵。

我们会发现。 对于一个点,包含多少个矩阵是与他可以组成矩阵的点的个数。

BWBBB

WWBBW

WWBWW

WWWWW

看这组样例的最后一行,W的高度分别是 3 4 1 2 3.那么对于这一行的点来说可以组成多少个子矩阵呢?

(3,0)这个肯定是3没问题。(3,1)这个高度是4,而(3,0)是3,所以最多可以组成7个。(3,2)这个高度是1,那么与前面的连起来。

只能使用3 4中分别一个,总共3个,对于(3,3)这个,因为前面的1比他小所以1可以用的点 2一定也可以用再加上2,总共是5.

对于3来说。前面有个2了。那么2可以用的点3一定可以直接用。所以是8.

我们可以看出。对于某一个行,我们需要维护一个单调递增的序列。当对于一个位置的数的时候,去寻找小于等于这个数的最大的数。比如3可以先找到2。

直接用当前的高度加上这个比自身小的点的数量就好了。当栈中最大的元素大于当前的元素的时候。 出栈同时加上自身的大小(比如前面有个4,现在是3,这个3可以用4中的3个来组成矩阵)。

但是像下面这组数据

wbb
wwb
www

对于最后一行,高度为3 2 1.我们用单调栈来模拟一下。3进栈。(2, 0)是3,对于2来说,3大了。出栈,2进栈。(2,1)是4.对于1来说。2出栈,1进栈,(2,2)是2.但是(2,2)是错的。

问题就出在。我们把3这个元素已经提前弹出栈了。在1访问栈的时候,没有访问到3.所以少了1.这里我们还需要一个数组来维护在该位置前面大于该元素的数的个数。

 

 

1 条评论

欢迎留言

*