最小面积矩阵

思路

这一题还是有些复杂的，先说一下大致思路：

• 任选两列，把这两列间的元素相加成一列，即一维数组，实际宽度为 j - i + 1
• 遍历一维数组，找到和大于等于 K 的最短连续子序列，长度为 len
• 那么上面对应的子矩阵的面积为 (j - i + 1) * len
• 重复上述过程找到最小值

我们先来看一道这样的题目，求一维数组里，大于等于给定任意正整数 K 的最短连续子序列的长度。我们可以用两个指针初始化指向头部，然后 end 指针逐渐后移，直到符合条件的子序列出现，记录当前的长度，然后前指针后移，直到 sum < K，之后 end 指针继续后移。一遍下来就可以完成目标。

我们再来看这道题，我们看看能不能将二维数组降维，选出任意两列，将这两列之间每行的元素相加，得到一个一维数组，对这个一维数组运用上面的最短连续子序列和的算法。时间为O(n),选择任意两列的时候，两个for循环，时间为O(n*2)

#include <iostream>  
#include <cstring>

using namespace std;  

int matrix[110][110];  
int num[110]; 
int N, M, K;

// 将第 i 列和第 j 列之间的元素相加得到一维数组
void merge(int i,int j){  
    for(int p = 0; p < N; p ++){  
        for(int k = i; k <= j; k ++){  
            num[p] += matrix[p][k];  //合并成一维数组   
        }  
    }  
}  
// 在一维数组中寻找大于等于 K 的最短连续子序列
int findShortest(){  
    int start = 0 ,end = 0;  
    int sum = 0, ans = N + 1;   
    bool flag = false;  
    while(end < N){  
        if(sum < K){  
            sum += num[end];  
        }  
        while(sum >= K){  
            flag = true;  
            ans = min(ans, end-start+1);  
            sum -= num[start++];  
        }  
        end ++;  
    }  
    if(flag) return ans;  
    else return N*M;    //全部加起来值都没超过K   
}  

int main(){ 
    while(cin >> N >> M >> K){   
        int sum = 0;  
        // 初始化
        for(int i = 0; i < N; i ++){  
            for(int j = 0; j < M; j ++){  
                cin >> matrix[i][j];  
                sum += matrix[i][j];  
            }  
        }  
        if(sum < K)  
            cout << -1 << endl;  
        else{  
            int minArea = N * M;  
            for(int i = 0; i < M; i ++){  
                for(int j = i; j < M; j ++){
                    // 选择任意两列进行合并
                    memset(num, 0, sizeof(num));  
                    merge(i, j); 
                    // 在一维数组中进行查找
                    int temp = findShortest();  
                    temp = (j - i + 1) * temp;  
                    minArea = min(minArea, temp);  
                }  
            }  
            cout << minArea << endl;  
        }     
    }  
    return 0;  
}