学步园

原题大意为：在一个N阶（N*M也同理）的矩阵中，所有元素为1或0，请找出全为1的最大矩阵（K*K）；

void deleteArray(int** arrary,int n)
{
	assert(arrary!=NULL&&n>0);
	for(int i=0;i<n;i++)
	{
		delete[] arrary[i];
		arrary[i]=0;
	}
	delete[] arrary;
}

int findAll1MatrixWidth(int ** M,int n)
{
	assert(M!=NULL&&n>=0);
	int i=0;
	for( ;i<n;i++)
		assert(M[0]!=NULL);

	int** Acc=new int*[n];
	for (i=0;i<n;i++)
		Acc[i]=new int[n];

	int j=0;
	for (i=0;i<n;i++)
		Acc[0][i]=M[0][i];
	for (i=1;i<n;i++)
		for (j=0;j<n;j++)
			Acc[i][j]=M[i][j]+Acc[i-1][j];

	int res=0;
	for (i=0;i<n;i++)
	{
		for (j=i;j<n;j++)
		{
			int rows=j-i+1;
			int cols=0;
			int k=0;
			for (;k<n;k++)
			{
				if (Acc[j][k]-Acc[i][k]+M[i][k]==rows)
					++cols;
				else
					cols=0;
				if (cols==rows)
					break;
			}
			if (cols ==rows )
				res=::max(res,rows);
		}
	}
	deleteArray(Acc,n);
	return res;
}

这是O(N^3)但空间是O(N^2)的算法。

=====================更新======================

今天做了largest Rectangle in a HIstogram之后，发现如果利用该算法的话可以将本体的复杂度降为o(n2)。

其中largestRectangleArea()函数来自那篇文章。

新的代码如下：

int maximalRectangle(vector<vector<char> >& mat)
	{
		if (mat.empty()) return 0;
		int m=mat.size();
		int n=mat[0].size();
		vector<vector<int> > grid(m,vector<int>(n,0));

		int i,j;
		for(i=0;i<n;i++)
			grid[0][i]=mat[0][i]-'0';
		for(i=1;i<m;i++)
		{
			for(j=0;j<n;j++)
			{
				if (mat[i][j]=='0')
					grid[i][j]=0;
				else
				{
					grid[i][j]=grid[i-1][j]+mat[i][j]-'0';
				}	
			}
		}

		int ans=0;
		for(i=0;i<m;i++)
		{
			int curMax=largestRectangleArea(grid[i]);
			ans=max(ans,curMax);
		}
		return ans;
	}