最大的长方形

/*
	 * 本体解法基于84. Largest Rectangle in Histogram
	 * 把每一行看成求直方图中最大矩形面积问题
	 */
	public int maximalRectangle(char[][] matrix) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
			return 0;
		int m = matrix.length, n = matrix[0].length;
		int max = 0;
		int[] h = new int[n];
		for (int i = 0; i < m; i++) {
			Stack<Integer> stack = new Stack<Integer>();
			stack.push(-1);
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1')
					h[j] += 1;
				else
					h[j] = 0;

			}
			for (int j = 0; j < n; j++) {
				while (stack.peek() != -1 && h[j] < h[stack.peek()]) {
					int top = stack.pop();
					max = Math.max(max, (j - 1 - stack.peek()) * h[top]);
				}
				stack.push(j);
			}
			while (stack.peek() != -1) {
				int top = stack.pop();
				max = Math.max(max, (n - 1 - stack.peek()) * h[top]);
			}
		}
		return max;
	}

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int ret = 0;
        if(matrix.empty()|| matrix[0].empty()){
            return ret;
        }
        
        int m = matrix.size();
        int n = matrix[0].size();
        
        for(int i = 0; i < m; i++){
            vector<int> temp(n, 0);
            for(int j = 0; j < n; j++){
                int r = i;
                while(r>=0 && matrix[r][j] == '1'){
                    temp[j]++;
                    r--;
                }
            }
            ret = max(ret, largestRectangleArea(temp));
        }
        return ret;
    }
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        int result = 0;
        stack<int> s;
        for(int i = 0; i < heights.size(); ){
            if(s.empty() || heights[i] >= heights[s.top()]){
                s.push(i);
                i++;
            }else{
                int temp = s.top();
                s.pop();
                result = max(result, (s.empty() ? i : i-s.top()-1)*heights[temp]);
            }
        }
        return result;
    }
};

//参考最高票Java版答案，主要思路就是直方图求最大面积
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.size()==0)
            return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> h(n);
        int maxS = 0;
        int num;
        stack<int> st;
        st.push(-1);
        for(int i=0;i<m;i++)
        {
              //求当前第i行往上连续1的个数，不连续就置为0，方便下一行统计
              //j表示列号，即直方图的连续序号
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='1')
                    h[j]++;
                else
                    h[j] = 0;
            }
            for(int j=0;j<n;j++)
            {
                      //这里主要思路是遇到上升序列就入栈，遇到下降序列就计算当前前一个直方图(即当前栈顶序号)
                      //到所有依次出栈（即降序且大于j指向直方图的高度）直方图的距离，然后乘以出栈直方图的高度，
                       //即为当前的面积(不一定最大),剩下的序列依然是升序的，迭代下去
                while(st.top()!=-1 && h[j]<h[st.top()])
                {
                    num = st.top();
                    st.pop();
                    maxS = max(maxS,(j-1-st.top())*h[num]);
                }
                st.push(j);
            }
               //计算栈中最后一个上升序列的面积（方法同上）
            while(st.top()!=-1)
            {
                num = st.top();
                st.pop();
                maxS = max(maxS,(n-1-st.top())*h[num]);
            }
        }
        return maxS;
    }
};

    /*
    * 目的：最大区域面积
    * 方法：参考leetCode的答案，将每一行都看成一个直方图，最后求直方图所能组成的最大面积
    */
    int maximalRectangle(vector<vector<char> > &matrix) {
        int maxVal = 0;
        int row = matrix.size();
        if (row==0)
            return 0;
        int col = matrix[0].size();
        stack<int>store;
        vector<int>height(col);
        for (int i = 0; i < row; ++i){
            for (int j = 0; j < col;++j){
                if (matrix[i][j] == '1'){
                    height[j]++;
                }
                else{
                    height[j] = 0;
                }
            }
            for (int j = 0; j < col; ++j){
                while(!store.empty() && height[j]<height[store.top()]){
                    int index = store.top();
                    store.pop();
                    int k = store.empty()?-1:store.top();
                    int area = (j-k-1)*height[index];
                    maxVal = max(area,maxVal);
                }
                store.push(j);
            }
            while(!store.empty()){
                int index = store.top();
                store.pop();
                int k = store.empty()?-1:store.top();
                int area = (col-k-1)*height[index];
                maxVal = max(area,maxVal);
            }
        }
        return maxVal;
    }

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int rows = matrix.size();
        if(rows <= 0 ) return 0;
        int cols = matrix[0].size(),maxH[cols];
        int maxArea = 0;
        for (int m = 0; m < rows; m ++) {
            for (int i = 0; i < cols; i++) {
                if (matrix[m][i] == '1') maxH[i] = 1;
                else maxH[i] = 0;
            }
            for (int j = 0; j < cols; j++) {
                int w = 1,l = j - 1, r = j + 1;
                while (l >= 0 && maxH[l] <= maxH[j] && maxH[l] > 0)   {l--;w++;}
                while (r < cols && maxH[r] <= maxH[j] && maxH[r] > 0) {r++;w++;}
                if (w * maxH[j] > maxArea) maxArea = w * maxH[j];
            }
            for (int i = m+1; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (matrix[i][j] == '1' && maxH[j] > 0 ) {maxH[j]++;} 
                    else {maxH[j] = 0;}
                }
                for (int j = 0; j < cols; j++) {
                    int w = 1,l = j - 1, r = j + 1;
                    while (l >= 0 && maxH[l] <= maxH[j] && maxH[l] > 0) {l--;w++;}
                    while (r < cols && maxH[r] <= maxH[j] && maxH[r] > 0) {r++;w++;}
                    if (w * maxH[j] > maxArea) maxArea = w * maxH[j];
                }
            }
        }
        return maxArea;
    }
};

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        if(m==0 || n==0)
            return 0;
        
        int Max = (matrix[0][0]==1?1:0);
        int l = 0, r = n;         vector<int> h(n,0), left(n,0), right(n,n);
        
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
                h[j] = (matrix[i][j]=='1' ? h[j]+1:0);
                         l = 0;
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j] == '1')
                    left[j] = max(left[j], l);
                else{
                    left[j] = 0;
                    l = j + 1;                 }             }                          r = n;             for(int j=n-1;j>=0;j--)             {                 if(matrix[i][j] == '1')                     right[j] = min(right[j], r);                 else{                     right[j] = n;                     r = j;                 }             }                          for(int j=0;j<n;j++)                 Max = max(Max, h[j]*(right[j]-left[j]));         }         return Max;
    }
};

	

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {  
    if(matrix.size()==0) 
        return 0; 
    int cols = matrix[0].size(); 
    int* hist = new int[cols]();  
        // 以某一行为起头对应该列的最大矩形（列连续1个数）
    int max_ = 0;
    for(int i=0; i<matrix.size(); i++)  
    {  
        for(int j=0; j<cols; j++)  
        {  
            if(matrix[i][j]=='1')  
                hist[j] += 1;  
            else  
                hist[j] = 0;  
        }
        max_ = max(max_, maxRectInHistogram(hist, cols) );  
    }
    delete [] hist;
    hist = nullptr;
    return max_;  
}  
int maxRectInHistogram(int hist[], int n)
{    
        int* arr = new int[n];// 申请一个额外的数组  以i为结尾的最大面积
        arr[0] = hist[0];    
        int m = hist[0]; // 最大面积    
        for(int i=1; i<n; i++)    
        {    
                arr[i] = hist[i];
                int temp = hist[i];
                for(int j=i-1; j>=0 && hist[j] > 0; j--)
                {
                    temp = min(temp,hist[j]);
                    arr[i] = max(arr[i],temp*(i-j+1));
                }
                if(m < arr[i])
                        m = arr[i];
        }
        delete [] arr;
        arr = nullptr;
        return m;    
}
};

// 从有“1”的地方开始搜索
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0)
        	return 0;
        
        int max = 0;
        for(int i = 0; i < matrix.length; i++){
        	for(int j = 0; j < matrix[0].length; j++){
        		if(matrix[i][j] == '0')
        			continue;
        		int width = Integer.MAX_VALUE;
        		for(int p = i; p < matrix.length; p++){
        			if(matrix[p][j] == '0')
            			break;
        			for(int q = j; q < matrix[0].length; q++){
        				if(matrix[p][q] == '0' || q == matrix[0].length - 1){
        					int curwid;
        					if(matrix[p][q] == '1')
        						curwid = q - j + 1;
        					else 
        						curwid = q - j;
        					if(curwid < width)
        						width = curwid;
        					int curS = width * (p - i + 1);
        					if(curS > max)
        						max = curS;
        					break;
        				}
        			}
        		}        		
        	}
        }
        return max;
    }
}

    }

//最渣的版本
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.size()==0) return 0;
        int rows=matrix.size();
        int cols=matrix[0].size();
        int MAX=0;
        vector<int >temp(cols,0);
        vector<vector<int > >result;
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                
                temp[j]=matrix[i][j]-'0'+(matrix[i][j]-'0')*temp[j];
            }
            MAX=max(largestRectangleArea(temp),MAX);
        }
        return MAX;
    }
    int largestRectangleArea(vector<int> &height) {
        int MAXAREA=0;
        for(int i=0;i<height.size();i++)
        {   int MIN=height[i];
            for(int j=i;j<height.size();j++)
            {
                
                MIN=min(MIN,height[j]);
                int CurArea=MIN*(j-i+1);
                if(CurArea>MAXAREA)
                {
                    MAXAREA=CurArea;
                }
            }
        }
        return MAXAREA;
    }
};

从这个问题想到单调栈结构确实有点不容易，我们举例说明：

1. 0 0 1 1 0 1 1
2. 0 0 1 1 1 0 1
3. 0 1 1 1 1 1 0
4. 1 0 0 0 0 1 1

然后将每个元素转化为该元素及上面相连的1的个数和：

1. 0 0 1 1 0 1 1
2. 0 0 2 2 1 0 2
3. 0 1 3 3 2 1 0
4. 1 0 0 0 0 2 1

以第3行为例，转化成柱形图，下图：

是不是很熟悉呢？对的，其实这就是单调栈结构的一个典型应用，以求上面图片中最大矩形面积为例，单调栈的实现如下（建议作为单调栈题目的模版去记忆）：

int monotoneStack(vector<int> &vec) {
    stack<int> st;
    vec.push_back(0);   // ➤ 添加一个0可以在循环的最后一步清空栈
    int maxVal = 0;
    for (int i = 0; i < vec.size(); ++i) {
        // 这里用单调递增栈
        while (!st.empty() && vec[i] < vec[st.top()]) {
            int height = vec[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - (left+1);
            maxVal = max(maxVal, height * width);
        }
        st.push(i);
    }
    return maxVal;
}

完整代码如下：

//
// Created by jt on 2020/9/2.
//
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        vector<vector<int> > tmp(matrix.size(), vector<int>(matrix[0].size()));
        // 第一次遍历：将char型数组转化为int型数组
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                tmp[i][j] = matrix[i][j] - '0';
            }
        }

        // 第二次遍历：转化矩阵
        for (int i = 1; i < tmp.size(); ++i) {
            for (int j = 0; j < tmp[0].size(); ++j) {
                if (tmp[i][j] == 1) tmp[i][j] = tmp[i - 1][j] + 1;
            }
        }

        // 第三次遍历：单调递增栈求最大矩阵面积
        int maxVal = 0;
        for (int i = 0; i < tmp.size(); ++i) {
            maxVal = max(maxVal, monotoneStack(tmp[i]));
        }
        return maxVal;
    }

private:
    int monotoneStack(vector<int> &vec) {
        stack<int> st;
        vec.push_back(0);   // ➤ 添加一个0可以在循环的最后一步清空栈
        int maxVal = 0;
        for (int i = 0; i < vec.size(); ++i) {
            // 这里用单调递增栈
            while (!st.empty() && vec[i] < vec[st.top()]) {
                int height = vec[st.top()];
                st.pop();
                int left = st.empty() ? -1 : st.top();
                int width = i - (left+1);
                maxVal = max(maxVal, height * width);
            }
            st.push(i);
        }
        return maxVal;
    }
};

//利用Largest Rectangle in Histogram的思想，可参考
//https://www.bilibili.com/video/BV1eb411M7Gm?from=search&seid=5986427457100938076
//若matrix有m行，则可以把问题分解成m个Largest Rectangle in Histogram问题
//从上到下遍历matrix的每一行，第i行往上的部分可以看做是Largest Rectangle in Histogram问题中的一个柱形图

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int m=matrix.size();
        if(m==0)
            return 0;
        int n=matrix[0].size();
        stack<int>st;
        st.push(-1);
        int max_area=0;
        vector<int>heights(n,0);
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(matrix[i][j]=='1')
                    heights[j]++;
                else
                    heights[j]=0;
            }
            for(int j=0;j<n;++j)
            {
                while(st.top()!=-1&&heights[j]<heights[st.top()])
                {
                    int index=st.top();
                    st.pop();
                    max_area=max(max_area,heights[index]*(j-1-st.top()));
                }
                st.push(j);
            }
            while(st.top()!=-1)
            {
                int index=st.top();
                st.pop();
                max_area=max(max_area,heights[index]*(n-1-st.top()));
            }
        }
        return max_area;
    }
};

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        if(n == 0 || m == 0)
            return 0;
        int max_rec = 0;
        vector<int> h(m,0);
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(matrix[i][j] == '1')
                    h[j]++;
                else
                    h[j] = 0;
            }
            stack<int> sta;
            sta.push(-1);
            for(int j = 0; j < m; ++j){
                while(sta.top()!= -1 && h[sta.top()] > h[j]){
                    int tmp = sta.top();
                    sta.pop();
                    max_rec = max(max_rec, (j - sta.top()-1)*h[tmp]);
                }
                sta.push(j);
            }
            while(sta.top()!=-1){
                int tmp = sta.top();
                sta.pop();
                max_rec = max(max_rec, (m - sta.top()-1)*h[tmp]);
            }
        }
        return max_rec;
    }
};

import java.util.Stack;
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix==null||matrix.length==0)return 0;
        int row = matrix.length,col = matrix[0].length;
        int max = 0;
        int[] heights = new int[col];
        for(int i = 0;i < row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i][j]=='1')
                    heights[j]++;
                else
                    heights[j] = 0;
            }
            max = Math.max(max,getMaxRectangle(heights));
        }
        return max;
    }
    
    public int getMaxRectangle(int[] heights){
        int n = heights.length;
        int max = 0,j,k,curMax;
        Stack<Integer> stk = new Stack<>();
        for(int i=0;i<n;i++){
            while(!stk.isEmpty()&&heights[stk.peek()]>=heights[i]){
                j = stk.pop();
				k = stk.isEmpty()?-1:stk.peek();
				curMax = (i-k-1)*heights[j];
               // curMax = (i-j)*heights[j];    错误的更新
				max = Math.max(curMax, max);
            }
            stk.push(i);
        }
        while(!stk.isEmpty()){
            j = stk.pop();
            
			k = stk.isEmpty()?-1:stk.peek();
			curMax = (n-k-1)*heights[j];
            //curMax = (n-j)*heights[j];    错误的更新
			max = Math.max(curMax, max);
        }
        return max;
    }
    
}