首页 > 代码库 > 51nod1158 单调栈 个人的想法以及分析

51nod1158 单调栈 个人的想法以及分析

单调栈,顾名思义就是保持内部元素单调性并且保证FILO的一种数据结构。 单调栈的代码实现没有什么难度,但是使用姿势难以想到。

在51nod1158中描述了这样一个问题: 给定一个 0-1 矩阵, 求这个矩阵最大的全 1 子矩阵的面积。

问题十分好理解。 

现在,我们将这个问题拆分成一些子问题来逐个击破。

首先,为了保证程序操作的规律性与有序性,我们需要把问题等价成一个任意规模下的问题。 比如我们可以将其等价为:

  对于第 i 行(列), 求出 以它为边界的最大全 1 子矩阵面积。

  这样子我们最终所需要的其实是 max(ansi);

接下来解决 i 规模下的问题:

  由于矩阵其实是一种二维结构,对二维结构的处理是十分复杂并且耗时的,所以我们考虑把二维的问题转变为一维的问题。

  这样子我们肯定没有办法直接处理。 由于题目要求的是求出子矩阵面积, 所以我们考虑对于一个点 (i,j), 它周围会有多大的全1矩阵。

  首先我们需要在行和列上对 (i,j)  覆盖范围进行扩展。 那么我们自然而然会想到统计的方法。 即统计出行上扩展的长度,以及在此基础上列扩展的长度。

  扩展行的长度比较容易,我们只需要预处理矩阵。 对于 (i,j) 定义 cnt[i][j] 表示它在行上扩展的长度。 则容易得到递推式 cnt[i][j] = (a[i][j] == 1 ? cnt[i][j-1] + 1 : 0)

  列扩展的难点在与需要依赖与行扩展的结果。 每次所扩展的范围一定是扩展到一个离 ( i , j ) 最远的行扩展不为 0 的位置。 这个很好理解,然后用行扩展乘列扩展就是最终答案。

  那我们现在的问题转化为如何求解列扩展。

  对于位置 ( i , j ) 我们已知它的行扩展为 cnt[i][j] 那么我们考虑以位置 ( i, j ) 为起点向 ( i , j-1 ) 的方向扩展。 在这个方向上与位置 ( i , j ) 相连且行扩展大于 cnt[i][j] 的列号都是可扩展列。

  所以我们此时需要找到所有 j 列之前的列扩展大于 cnt[i][j] 的列, 程序上来讲就是实现一个单调减栈, 每次入栈 ( i , j ) 时必定会先弹出大于cnt[i][j] 的元素。

  我们从 ( i, j ) 开始向左扩展, 再向右扩展, 就得到了最终的结果。

  代码如下:

  

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 510;
 4 int a[maxn][maxn];
 5 int tmp[maxn][maxn];
 6 int up[maxn], down[maxn];
 7 int main(){
 8     int m,n;
 9     cin >> m >> n;
10     for(int i = 1; i <= n; i++){
11         for(int j = 1; j <= m; j++){
12             scanf("%d", &a[i][j]);
13         }
14     }
15     for(int i = 1; i <= n; i++){
16         for(int j = 1; j <= m; j++){
17             if(a[i][j]) tmp[i][j] = tmp[i][j-1] + 1;
18         }
19     }
20     int ans = 0;
21     for(int j = 1; j <= m; j++){
22         for(int i = 1; i <= n; i++){
23             int cur = i-1;
24             for(; cur && tmp[i][j] <= tmp[cur][j]; cur = up[cur]);
25             up[i] = cur;    
26         }
27         for(int i = n; i > 0; i--){
28             int cur = i + 1;
29             for(; cur <= n && tmp[i][j] <= tmp[cur][j]; cur = down[cur]);
30             down[i] = cur;     
31         }
32         for(int i = 1; i <= n; i++){
33             ans = max(ans, (down[i] - up[i] - 1) * tmp[i][j]);
34         }
35     }    
36     cout << ans << endl;
37     return 0;
38 }    

 

51nod1158 单调栈 个人的想法以及分析