在矩阵中寻找最大正方形连续区域
 
 
问题描叙
 
 
 
输入一个矩阵M、一个数字k，找出一个最大的正方形连续区域，这个区域里的数字均是k。 
 ​ 
  
  
 
 
 
 
界的思考
 
 
 
对于矩阵M中的每一个元素，要么等于k要么不等于k，要知道这个数的状态，必须有一次比较。一共n个数，所以至少需要$n^2$次比较。故比较次数的下界为$\Omega(n^2)$，那么是否存在一个$O(n^2)$的算法来解决这个问题呢？
 
 
算法
 
 
 
M中的每一个元素$M_{ij}$都有一个与之对应的数值$max_{ij}$记录着以这个元素为左上角顶点的最大的一个正方形连续区域的大小(行/列 数)。 
 对元素$M_{ij}$有两种状态
 
 
$M_{ij}\ne k$ , 此时可以得出$max_{ij}=0$。
$M_{ij} = k$ , 此时可以得出$max_{ij}=min(max_{(i+1)j},max_{i(j+1)},max_{(i+1)(j+1)})+1$。
 
 
​ 
  
  
  
 
 从右到左，从下往上地扫描矩阵M，计算出每一个元素的
 
 $max_{ij}$，其中最大的
 
 $max_{ij}$就是矩阵M的最大正方形连续区域的大小，其对应的元素的下标(i,j)就是这块连续区域的左上角顶点。
 
 
 
内存使用
 
 
 
大可不必创建 $row \times column$ 个空间来存储每一个元素的$max_{ij}$，实际上，在比较过程中只用$min(row,column)+1$ 个内存空间就行了。
 
 
过程图示
 
 
 
例图: 
 ​ 
  
  
  
 
 第一轮循环: 
 
 ​ 
  
  
  
 
 第二轮循环: 
 
 ​ 
  
  
  
 
 第三轮循环: 
 
 ​ 
  
  
  
 
 用一个数据结构记录当前找到的最大的连续正方形的大小和对应的左上角坐标。 
 
 在比较的过程中，如果遇到更大的连续正方形，则更新记录。
 
 
 
代码
 
< header and helper >
 
#include<iostream>

using namespace std;

struct max_memo{//记录最大连续正方形区域的大小和左上角的坐标

    //左上角的坐标
    int row;
    int col;

    int num;//大小---以行or列为单位

};

//放回三个数中最小值。
int min(int left, int down, int leftdown){

    left = left < down ? left : down;

    return  left < leftdown ? left : leftdown;
}
 
< search >
 
void search(int M[][5],int k,int row,int col, max_memo &Max_memo){


    int *memo = new int[row]; 
    int up_one;
    int current;

    for (int i(0); i <row; i++){//初始化最后一行
        if (M[col - 1][row - 1 - i] == k)
            memo[i] = 1;
        else memo[i] = 0;
    }

    Max_memo.col = col - 1, Max_memo.row = row - 1, Max_memo.num = memo[0];//初始化

    int ex_index;//记录交换时的下标。

    for (int row_local(row - 2), col_local(col - 1); row_local >= 0;)//外循环。
    {

        col_local = (col - 1);//初始化列坐标---每次内循环从最右边开始，向左移动。

        if (M[row_local][col_local] == k) {
            up_one = 1;//计算最右端的元素的最大连续区域（0 or 1）

            if (up_one > Max_memo.num){
                Max_memo.col = col_local, Max_memo.row = row_local, Max_memo.num = up_one;//更新
            }
        }
        else up_one = 0;

        col_local--;

        while (col_local >= 0){//内循环

            ex_index = (col - 1) - col_local-1;

            if (M[row_local][col_local] != k){  
                current = 0;                
            }

            if (M[row_local][col_local] == k){

                current = min(up_one, memo[ex_index + 1], memo[ex_index]) + 1;
                if (current > Max_memo.num){
                    Max_memo.col = col_local, Max_memo.row = row_local, Max_memo.num = current;//更新
                }
            }

            memo[ex_index] = up_one;
            up_one = current;

            col_local--;//向左移       
        }

        memo[row - 1] = up_one;//第一轮循环结束。

        row_local--;//向上移
    }


    delete[] memo;
}
 
< main >
 
int main(){

    int M[][5] = {
    /*  { 0, 1, 1, 1, 1 },
        { 0, 1, 2, 2, 1 },
        { 1, 1, 2, 2, 1 },
        { 1, 1, 2, 2, 1 },
        { 1, 1, 0, 0, 1 }
    */
        {0,0,0,0,1},
        {0,0,0,0,1},
        {0,0,0,0,1},
        {0,0,0,0,1},
        {0,0,0,0,0}
    };

    max_memo Max_memo;

    int k = 1;

    search(M, k, 5, 5, Max_memo);

    if (Max_memo.num)
    cout << "结果: 坐标(" << Max_memo.row << ", " << Max_memo.col << "); 大小(以行为单位): " << Max_memo.num << endl;
    else cout << "没有值为"<<k<<"的连续正方形区域" << endl;


    cout << endl;
    system("pause");

}

题目：原题链接（困难）
 
标签：排序、数学
 
解法
时间复杂度
空间复杂度
执行用时
Ans 1 (Python)
$O(L^{2}log{L}^2)$
$O(L^2)$
60ms (57.14%)
Ans 2 (Python)
Ans 3 (Python)

解法一：
 
class Solution:
    def maximumNumberOfOnes(self, width: int, height: int, length: int, max_ones: int) -> int:
        nums = []
        for i in range(length):
            for j in range(length):
                a1, b1 = divmod(width, length)
                a2, b2 = divmod(height, length)
                c1 = a1 + (1 if b1 > i else 0)
                c2 = a2 + (1 if b2 > j else 0)
                nums.append(c1 * c2)
        nums.sort(reverse=True)
        return sum(nums[:max_ones])

数值1 在矩阵中的最大数量是多少，现有一个尺寸为sideLength*sideLength 的矩阵M,矩阵中的每个单元格的值不是0就是1，而且知道矩阵
 的边长maxOnes，计算矩阵中最多可以有多少个1
 参考：//https://leetcode.com/savevmk
 根本看不懂
 
class Solution(object):
    def maximumNumberOfOnes(self,width: int,height: int, sideLength:int,maxOnes:int) -> int:
        arr = [0 for _ in range(sideLength*sideLength)]
        for i in range(height):
            for j in range(width):
                row = i%sideLength
                col = j%sideLength
                arr[row*sideLength +col]+=1
        arr.sort()# 升序
        ans=0
        for i in range(maxOnes):
            ans += arr[len(arr) -1 -i] # 1的个数
        return ans

if __name__ == '__main__':
    width,height,sideLength,maxOnes = 2,1,4,2
    print(Solution().maximumNumberOfOnes(width,height,sideLength,maxOnes))

来自牛客网左程云第三课第一题
 
问题：给定一个无序矩阵，其中有正，有负，有 0，求子矩阵的最大和。
 
要求：时间复杂度O(N^3)
 
分析：一个最直接的方法就是找到所有的子矩阵，然后遍历这些子矩阵并计算其累加和，找出最大的。矩阵将矩阵中的每一个点作为子矩阵的左上角，我们可以得到N*N的数量级的子矩阵数量。那么一共有N*N个点可以作为子矩阵的左上角，子矩阵的数量到达O(N^4)的数量级，我们在计算每个子矩阵的时候累加和的时候需要遍历每一个数，达到O(N*N)的数量级，整体的时间复杂度达到O(N^6)。子矩阵我们都可以转换成子数组解决，这道题的算法原型是leetcode 53. Maximum Subarray 子数组最大和。
 
解法：我们求出以每一行的为首行的子矩阵的列累加和，就是将列对应相加，这样我们就得到了一个数组，接下来我们求这个数组的子数组最大和也就是求出了这个子矩阵的最大和。那么我们一共有N行，以这些行为首行的子矩阵有N*N个，求子数组最大和的时间复杂度为O(N)，整体的时间复杂度为O(N^3)。算法原型真的是很重要啊。
 

public class Main {
	public static int maxSum(int[][] m) {
		if (m == null || m.length == 0 || m[0].length == 0) {
			return 0;
		}
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < m.length; i++) {
			for (int j = i; j < m.length; j++) {
				int sum = 0;
				for (int k = 0; k < m[j].length; k++) {
					if (i != j) {
						m[i][k] += m[j][k];// 把累加结果保存在当前行
					}
					sum += m[i][k];
					max = Math.max(max, sum);
					sum = sum > 0 ? sum : 0;
				}
			}
		}
		return max;
	}

	public static void main(String[] args) {
		int[][] matrix = { { -90, 48, 78 }, { 64, -40, 64 }, { -81, -7, 66 } };
		System.out.println(maxSum(matrix));

	}
}