左神算法进阶班3_2求最大矩阵

逃离我推掉我的手 2022-01-05 23:55 133阅读 0赞

**【题目】**  
　　给定一个整型矩阵map，其中的值只有0和1两种，求其中全是1  
　　的所有矩形区域中，最大的矩形区域为1的数量。  
　　例如：  
　　　　1 1 1 0  
　　其中，最大的矩形区域有3个1，所以返回3。  
　　再如：  
　　　　1 0 1 1  
　　　　1 1 1 1  
　　　　1 1 1 0  
　　其中，最大的矩形区域有6个1，所以返回6。

**【解】**  
　　使用单调栈  
　　栈序为从小到大顺序。  
　　将矩阵从第一行向下将每一行进行累加，新的行中为0则其累加和为0  
　　利用单调栈进行计算出每一行的累加和的最大矩阵  
　　如上例的第一行累加和数组为\[1,0,1,1\]  
　　第二行累加和数组为\[2,1,2,2\]  
　　第三行累加和数组为\[3, 2, 3, 0\];

**【Code】**

**　　**

1 #pragma once
     2 #include <iostream>
     3 #include <vector>
     4 #include <deque>
     5 
     6 using namespace std;
     7 
     8 int MaxRecArea(const vector<vector<int>>v)
     9 {
    10     vector<int>Sum(v[0].size(),0);//储存每行的累加和
    11     int res = 0;
    12     for (int i = 0; i < v.size(); ++i)
    13     {
    14         for (int j = 0; j < v[0].size(); ++j)
    15             Sum[j] = v[i][j] == 0 ? 0 : (Sum[j] + v[i][j]);
    16 
    17         deque<int>d;//单调栈
    18         for (int j = 0; j < Sum.size(); ++j)
    19         {
    20             while (!d.empty() && Sum[j] <= Sum[d.back()])//维持栈为从小到大的排序
    21             {
    22                 int index = d.back();
    23                 d.pop_back();
    24                 if (d.empty())//弹出的数能到最左边-1的位置
    25                     res = res > (Sum[index] * j) ? res : (Sum[index] * j);
    26                 else//弹出的数有左边界
    27                     res = res > (Sum[index] * (j - d.back() - 1)) ? res : (Sum[index] * (j - d.back() - 1));
    28             }
    29             d.push_back(j);
    30         }
    31         while (!d.empty())//弹出剩余的数，其都无右边界，右边界为数组的大小
    32         {
    33             int index = d.back();
    34             d.pop_back();
    35             if (d.empty())//弹出的数能到最左边-1的位置
    36                 res = res > (Sum[index] * Sum.size()) ? res : (Sum[index] * Sum.size());
    37             else//弹出的数有左边界,
    38                 res = res > (Sum[index] * (Sum.size() - d.back() - 1)) ? res : (Sum[index] * (Sum.size() - d.back() - 1));
    39         }
    40     }
    41     return res;
    42 }
    43 
    44 
    45 
    46 void Test()
    47 {
    48     vector<vector<int>>v;
    49     v = { { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 0, 1, 1 }, };
    50     cout << MaxRecArea(v) << endl;
    51 
    52 }

转载于:https://www.cnblogs.com/zzw1024/p/11052496.html