leetcode Maximal Rectangle 单调栈

作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4052721.html

该题目是 leetcode Largest Rectangle in Histogram 的二维版本，首先进行预处理，把一个n×m的矩阵化为n个直方图，然后在每个直方图中计算使用单调栈的方法计算面积最大的矩形，然后求得最大的矩形面积即可。

Ps：这题直接在网页里面敲完居然1A，不错。

代码如下：

 class Solution {

 public:

 int mr(vector<int> arr)

 {

     arr.push_back();

     stack<pair<int, int> > st;//height index

     int res = ;

     for( int i =  ; i < arr.size() ; i++ )

     {

         pair<int, int> tmp;

         if( st.size() ==  || st.top().first <= arr[i] )

         {

             st.push(make_pair(arr[i], i));

         }

         else

         {

             while( st.size() >  && st.top().first > arr[i] )

             {

                 tmp = st.top();

                 st.pop();

                 res = max(res, tmp.first*(i-tmp.second));

             }

             st.push(make_pair(arr[i], tmp.second));

         }

     }

     return res;

 }

 int maximalRectangle(vector<vector<char> > &matrix)

 {

     int res = ;

     if( matrix.size() ==  ) return ;

     vector<vector<int> > ma(matrix.size(), vector<int>(matrix[].size(), ));

     for( int i =  ; i < matrix[].size(); i++ )

     {

         if( matrix[][i] == '' ) ma[][i] = ;

     }

     for( int i =  ; i < matrix.size() ; i++ )

     {

         for( int j =  ; j < matrix[].size() ; j++ )

         {

             if( matrix[i][j] == ''  )

             {

                 ma[i][j] = ma[i-][j] + ;

             }

         }

     }

     for( int i =  ; i < ma.size() ; i++ )

     {

         res = max(res, mr(ma[i]));

     }

     return res;

 }

 };

巴特西

leetcode Maximal Rectangle 单调栈

最新文章

热门文章