求最大子矩阵的大小_

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

struct P{
    int x,y;
};

int F(int *a, int m){
    int Max = 0, t;
    stack<P> S;
    for(int i=0;i<m;i++){
        while(!S.empty()){
            P p = S.top();
            if(p.y<a[i])
                break;
            S.pop();
            t = S.empty()?-1:S.top().x;
            Max = max(Max, (i-1-t)*p.y);
        }
        S.push(P{i, a[i]});
    }
    while(!S.empty()){
        P p = S.top();
        S.pop();
        t = S.empty()?0:S.top().x+1;
        Max = max(Max, (m-t)*p.y);
    }
    return Max;
}

int main(){
    int n, m, x, Max=0;
    cin>>n>>m;
    int dp[m];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>x;
            dp[j] = (x?dp[j]+1:0);
        }
        Max = max(Max, F(dp, m));
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2020-02-10 02:08:29 回复(0)

C

helloxuanbao

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef struct
{
    int *data;
    int top;
} stack;

void init_stack(stack *stp, int *arr);
void push(stack *stp, int val);
int pop(stack *stp);
int peek(stack *stp);
bool is_empty(stack *stp);

int max_area(const int *height, int n)
{
    int i, j, curArea, maxArea = 0, *data;
    stack st = {0}, *stp = &st;
    data = (int *) malloc(n * sizeof(int));
    init_stack(stp, data);
    for (i = 0; i < n; i++)
    {
        while (!is_empty(stp) && height[i] < height[peek(stp)])
        {
            j = pop(stp);
            curArea = height[j] * (i - (is_empty(stp) ? -1 : peek(stp)) - 1);
            maxArea = MAX(maxArea, curArea);
        }
        push(stp, i);
    }
    while (!is_empty(stp))
    {
        j = pop(stp);
        curArea = height[j] * (n - (is_empty(stp) ? -1 : peek(stp)) - 1);
        maxArea = MAX(maxArea, curArea);
    }
    free(data);
    return maxArea;
}

int main(void)
{
    int n, m, *height, i, j, tmp, res = 0;
    scanf("%d%d", &n, &m);
    height = (int *) calloc(m, sizeof(int));
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            scanf("%d", &tmp);
            height[j] = tmp == 0 ? 0 : (height[j] + 1);
        }
        tmp = max_area(height, m);
        res = MAX(res, tmp);
    }
    printf("%d\n", res);
    free(height);
    return 0;
}

void init_stack(stack *stp, int *arr)
{
    stp->data = arr;
    stp->top = -1;
}

void push(stack *stp, int val)
{
    stp->data[++stp->top] = val;
}

int pop(stack *stp)
{
    return stp->data[stp->top--];
}

int peek(stack *stp)
{
    return stp->data[stp->top];
}

bool is_empty(stack *stp)
{
    return stp->top == -1;
}

发表于 2022-07-24 23:45:33 回复(0)

Kai21

思路非常好懂，遍历每一行，以当前行为底，统计在此行之上连续的1的个数，像直方图一样；此时，问题重新转化为单调栈问题，时间和空间复杂度为O(M)。再考虑有N行，则总的时间复杂度为O(N*M)，上代码：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int arr[n][m];
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> arr[i][j];
        }
    }
    
    int row[m];
    memset(row, 0, m*sizeof(int));
    int max_square = 0;    // 返回的最大面积
    
    for(int i=0; i<n; i++){
        // 计算当前行的统计直方图的值, 0 或 1
        for(int j=0; j<m; j++){
            row[j] = arr[i][j]==0 ? 0 : row[j]+1;
        }

        stack<int> stk;
        for(int k=0; k<m; k++){
            while(!stk.empty() && row[stk.top()]>=row[k]){
                int index = stk.top();
                stk.pop();
                int left_index = stk.empty() ? -1: stk.top();
                int tmp_square = (k-left_index-1)*row[index];
                // 记录最大面积
                if(tmp_square > max_square)
                    max_square = tmp_square;
            }
            stk.push(k); // 加入新元素
        }
        // 清空栈内元素
        while(!stk.empty()){
            int index = stk.top();
            stk.pop();
            int left_index = stk.empty() ? -1 : stk.top();
            int tmp_square = (m-left_index-1)*row[index];
            // 记录最大面积
            if(tmp_square > max_square)
                max_square = tmp_square;
        }
        
    }
    cout<< max_square;
    return 0;
}

发表于 2020-02-26 10:41:59 回复(1)

EVANnnn1996

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
        /**
     * 时间复杂度O(N * M)
     */
    public static int maxRecSize(int[][] map) {
        // 排除三种特例： null 空数组[] 空数组[[]]
        if (map == null || map.length < 1 || map[0].length < 1) {
            return -1;
        }
        int n = map.length;
        int m = map[0].length;
        int[] height = new int[m];
        int maxArea = 0;
        // 统计从第i行开始每列往上有多少个连续的1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
            }
            maxArea = Math.max(maxRecFromBottom(height), maxArea);
        }
        return maxArea;
    }

    /**
     * 相当于寻找height中每个元素左边和右边的第一个比它小的元素，时间复杂度O(M)
     */
    private static int maxRecFromBottom(int[] height) {
        // 排除两种特例：null 空数组[]
        if (height == null || height.length < 1) {
            return -1;
        }
        // 单调栈初始化
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int cur;
        int rightLessIndex;
        int maxArea = 0;
        int curArea;
        while (i < height.length) {
            if (stack.isEmpty() || height[i] > height[stack.peek()]) {
                // 满足从栈顶到栈底单调递减时，压入
                stack.push(i);
                i++;
            } else {
                // 不满足栈顶到栈底单调递减时，淡出
                cur = stack.pop();
                rightLessIndex = stack.isEmpty() ? -1 : stack.peek();
                // 计算当前列及其左边最大子矩阵的大小
                curArea = (i - rightLessIndex - 1) * height[cur];
                maxArea = Math.max(curArea, maxArea);
            }
        }
        // 清算栈中剩余的元素，这些元素右边没有比它小的数字
        while (!stack.isEmpty()) {
            cur = stack.pop();
            rightLessIndex = stack.isEmpty() ? -1 : stack.peek();
            // 计算当前列及其左边最大子矩阵的大小
            curArea = (i - rightLessIndex - 1) * height[cur];
            maxArea = Math.max(curArea, maxArea);
        }
        return maxArea;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] numbers = bufferedReader.readLine().split(" ");
        int n = Integer.valueOf(numbers[0]);
        int m = Integer.valueOf(numbers[1]);
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            numbers = bufferedReader.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(numbers[j]);
            }
        }
        System.out.println(maxRecSize(map));
    }
}

发表于 2019-12-15 17:38:35 回复(0)

C++

木子蓝色

本题与LeetCode 85题相同，难的是边界条件的处理

#include <bits/stdc++.h>

using namespace std;

int maxArea(vector<int> height){
    stack<int> st;    
    int ans = 0;
    height.insert(height.begin(), 0);
    height.push_back(0);
    st.push(0);
    for(int i = 1; i < height.size(); ++i){
        // 维护一个从栈底到栈顶单调递增的栈
        while(height[st.top()] > height[i]){
            int mid = st.top();
            st.pop();
            int left = st.top();
            int right = i;
            // 底 * 高就是面积， 注意 right - left 这里要再 -1
            ans = max(ans, height[mid] * (right - left - 1));
        }
        st.push(i);     // 入栈的是下标
    }
    return ans;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> matrix[i][j];
        }
    }
    
    int ans = 0;
    vector<int> height(m);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            // 化为直方图
            if(matrix[i][j] == 1){
                height[j]++;
            }
            else {
                height[j] = 0;
            }
        }
        ans = max(ans, maxArea(height));
    }
    
    cout << ans;
    return 0;
}

发表于 2022-04-07 16:17:46 回复(0)

C++

麦芒2021

一行一行的处理：

处理到每一行时，把该行当成底，转化为直方图，求最大面积

用单调栈求直方图最大矩形面积，用递增栈，栈中放小标，遇到小值时，将栈中上一个弹出，并以此为高，左右都是比它矮的，所有宽度为i-top()-1（考虑相等的情况，需要循环弹出）

#include "bits/stdc++.h"
using namespace std;

int find(vector<int>& matrix)
{
    int len=matrix.size();
    stack<int> stk;
    int ret=0;
    for(int i=0;i<len;i++)
    {
        if(stk.size()==0||matrix[stk.top()]<=matrix[i])
        {
            stk.push(i);
        }
        else if(matrix[stk.top()]>matrix[i])
        {
            int height=matrix[stk.top()];
            while(matrix[stk.top()]==height)stk.pop();
            int area=height*(i-stk.top()-1);
            i--;
            ret=max(ret,area);
        }
    }
    return ret;
}

int main()
{
    int m;cin>>m;
    int n;cin>>n;
    //cout<<m<<' '<<n;
    vector<vector<int>> matrix0(m,vector<int>(n+2,0));
    int tmp;
    int ret=0;
    //cout<<0;
    for(int i=0;i<m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>tmp;
            if(tmp==0) matrix0[i][j]=0;
            else if(i==0)matrix0[i][j]=tmp;
            else matrix0[i][j]=matrix0[i-1][j]+1;
        }
        //cout<<1;
        tmp=find(matrix0[i]);
        ret=max(ret,tmp);
    }
    cout<<ret;
    return 0;
    
}

发表于 2022-02-10 17:35:42 回复(0)

快支棱起来的椰子很愤怒

package main
import(
    "fmt"
)
func main(){
    var n, m int
    res := 0
    fmt.Scan(&n, &m)
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, m)
        for j := 0; j < m; j++ {
            fmt.Scan(&matrix[i][j])
        }
    }
    height := make([]int, m)
    for i := 0; i < n; i++ {
        stack := []int{}
        stack = append(stack, -1)
        for j := 0; j < m; j++ {
            if matrix[i][j] == 1 {
                height[j]++
            } else {
                height[j] = 0
            }
        }
        for x := 0; x < m; x++ {
            for len(stack) > 1 && height[x] <= height[stack[len(stack) - 1]] {
                index := stack[len(stack) - 1]
                stack = stack[:len(stack) - 1]
                left := stack[len(stack) - 1]

                temp := (x - left - 1) * height[index]
                if temp > res {
                    res = temp
                }
            }
            stack = append(stack, x)
        }
        for len(stack) > 1 {
            index := stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            left := stack[len(stack) - 1]
            temp := (m - left - 1) * height[index]
            if temp > res {
                    res = temp
                }
        }

    }
    fmt.Println(res)
}

发表于 2022-01-10 16:18:21 回复(0)

C++

五柳东坡

使用单调栈求解直方图的最大矩形面积。

#include <iostream>

#include <vector>
#include <stack>

using namespace std;

// 单调递增栈, 遇到一个齐平或者下降的元素则开始往回找,
// 找所有可能的左边界
int calMaxArea(const vector<int>& v) {
int maxArea = 0;
stack<int> s;
for (int i = 0; i < v.size(); i++) {
// 栈为空, 或者当前元素大于栈顶元素, 入栈
if (s.empty() || v[i] > v[s.top()]) {
s.push(i);
} else {
// 否则开始出栈, 计算矩形面积
while (!s.empty() && v[s.top()] >= v[i]) {
int idx = s.top();
s.pop();
// 若栈为空, 矩形左边界为-1
int left_idx = s.empty() ? -1 : s.top();
int tmpArea = ((i - 1) - left_idx) * v[idx];
if (tmpArea > maxArea) {
maxArea = tmpArea;
}
}
// i别忘记入栈
s.push(i);
}
}
return maxArea;
}

int main() {
int n = 0, m = 0;
cin >> n >> m;
vector<vector<int> > matrix(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matrix[i][j];
}
}
int maxValue = 0;
vector<int> tmpVec(m, 0);
for (int i = 0; i < n; i++) {
for (int c = 0; c < m; c++) {
if (matrix[i][c] == 1) {
tmpVec[c] += 1;
} else {
tmpVec[c] = 0;
}
}
int tmpMax = calMaxArea(tmpVec);
if (tmpMax > maxValue) {
maxValue = tmpMax;
}
}
cout << maxValue << endl;
return 0;
}

发表于 2021-12-08 22:23:47 回复(0)

Relili

今天吃我尸体,太难了

let [m,n]=readline().split(' ').map(item=>parseInt(item))
let matrix=Array.from({length:m},()=>Array(n))
// let dp=Array.from({length:m+1},()=>Array(n+1).fill(0))
 let index=0
while(index<m){
    matrix[index++]=readline().split(' ').map(item=>parseInt(item))
}

// let max=0
// for(let i=1;i<=m;i++){
//     for(let j=1;j<=n;j++){
//         if(matrix[i-1][j-1]==1&&matrix[i][j-1]==1&&matrix[i-1][j]==1){
//             dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+1
//         }
//        max=Math.max(max,dp[i][j])

//     }
// }

const getHeightArea=function(height){
    let fun_max=0
    let stack=[]

    for(let index=0;index<n;index++){
        while(stack.length&&stack[stack.length-1][1]>=height[index]){
             let [curIndex,curheight]=stack.pop()
             let k=stack.length>0?stack[stack.length-1][0]:-1
            fun_max=Math.max(fun_max,curheight*(index-(k+1)))
        }   
        stack.push([index,height[index]])
    }

    while(stack.length){
         let [curIndex,curheight]=stack.pop()
         let k=stack.length>0?stack[stack.length-1][0]:-1
         fun_max=Math.max(fun_max,curheight*(n-(k+1)))
    }
    return fun_max
}

let max=0

let height=Array(n).fill(0)
for(let i=0;i<m;i++){
    for(let j=0;j<n;j++){
        if(matrix[i][j]==1){
            height[j]+=1
        }else{
             height[j]=0
        }   
    }
    // console.log(height)
        max=Math.max(max,getHeightArea(height))

}

console.log(max)

发表于 2021-06-28 14:59:38 回复(0)

牛客517647993号

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int arr[n][m];
    int row[m];
    memset(row, 0, m*sizeof(int));
    int max_square = 0;    // 返回的最大面积
    
    for(int i=0; i<n; i++){
        // 计算当前行的统计直方图的值, 0 或 1
        for(int j=0; j<m; j++){
            cin >> arr[i][j];
            row[j] = arr[i][j]==0 ? 0 : row[j]+1;
        }

        stack<int> stk;
        for(int k=0; k<m; k++){
            while(!stk.empty() && row[stk.top()]>=row[k]){
                int index = stk.top();
                stk.pop();
                int left_index = stk.empty() ? -1: stk.top();
                int tmp_square = (k-left_index-1)*row[index];
                // 记录最大面积
                    max_square = max(tmp_square,max_square);
            }
            stk.push(k); // 加入新元素
        }
        // 清空栈内元素
        while(!stk.empty()){
            int index = stk.top();
            stk.pop();
            int left_index = stk.empty() ? -1 : stk.top();
            int tmp_square = (m-left_index-1)*row[index];
            // 记录最大面积
max_square = max(tmp_square,max_square);
        }
        
    }
    cout<< max_square;
    return 0;
}

发表于 2021-06-10 21:07:16 回复(0)

SuperDS

暴力求解：

public class Main {
    public static int getMaxMatrix(int[][] matrix) {
        // 最大子矩阵
        int[][] nums = new int[matrix.length][matrix[0].length];
        int sum = 0;
        // 首先将其进行初始化
        for(int i = 0 ; i < matrix.length ; i++){
            for(int j = 0 ; j < matrix[0].length ; j++){
                if( matrix[i][j] == 0 ){
                    sum = 0;
                }else{
                    sum+= 1;
                    nums[i][j] = sum;
                }
            }
        }
        int MAX = 0;
        // 初始化结束后进行求值
        for(int i = 0 ; i < nums.length ; i++){
            for(int j = 0 ; j < nums[0].length ; j++){
                int min = Integer.MAX_VALUE;
                int min_j = 0;
                // 然后是进行上遍历
                for(int t = 0; t < j ; t++){
                    if( min > nums[i][t]){
                        min = nums[i][t];
                        min_j = t;
                    }
                }
                MAX = Math.max(MAX ,min*(j - min_j + 1));
                // 然后是进行下遍历
                min = Integer.MAX_VALUE;
                min_j = j;
                for(int t = j; t < nums[0].length ; t++){
                    if( min > nums[i][t]){
                        min = nums[i][t];
                        min_j = t;
                    }
                }
                MAX = Math.max(MAX ,min*(j - min_j + 1));
            }
        }
        return MAX;
    }
}

发表于 2021-06-04 10:23:41 回复(0)

laugh_often

#include<bits/stdc++.h>

int mat[2001][2001];
int height[2001];
int left[2001];
int right[2001];
int main()
{
    
    int row, col;
    scanf("%d %d",&row,&col);
    int x = 0;
    for(int i = 0; i < row; ++i)
    {
        for(int j = 0; j < col; ++j)
        {
            scanf("%d",&x);
            mat[i][j] = x;
        }
    }
    int area = 0;
    memset(height,0,2001 * sizeof(int));
    for(int i = 0; i < row; ++i)
    {
        
        for(int j = 0; j < col; ++j)
        {
            if(mat[i][j] == 1)
                height[j] += 1;
            else
                height[j] = 0;
        }
        
        
        std::stack<int> st1;
        for(int j = 0; j < col; ++j)
        {
            while(!st1.empty() && height[st1.top()] >= height[j])
            {
                right[st1.top()] = j;
                st1.pop();
            }
            left[j] = (st1.empty() ? -1 : st1.top());
            st1.push(j);
        }
        
        for(int j = 0; j < col; ++j)
        {
            area = std::max(area,(right[j] - left[j] - 1) * height[j]);
        }
        
    }
    printf("%d\n",area);
    return 0;
}

发表于 2021-02-20 09:34:46 回复(0)

C/C++

cymm保佑拿理想offer

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    //vector<vector<int>>map(n,vector<int>(m,0));
      int cnt=0;
    //cout<<22<<endl;
    vector<int>height(m,0);
    int t;
    for(int i=0;i<n;i++){
        vector<int >sums(m,0);
        stack<int>s1,s2;
        for(int j=0;j<m;j++)
        {
            cin>>t;
            int h=(height[j]=t==0?0:1+height[j]);
            while(!s1.empty()&&h<=height[s1.top()]){
                
                s1.pop();
                
            }
            int l=s1.empty()?-1:s1.top();
            sums[j]+=(j-l)*h;
            printf("%d %d %d %d\n",i,j,j,sums[j]);


            s1.push(j);
            
            while(!s2.empty()&&h<height[s2.top()]){
                int p=s2.top();
                s2.pop();
                int r=j;
                sums[p]+=(r-p-1)*(height[p]);
                printf("%d %d %d %d\n",i,j,p,sums[p]);
                cnt=max(cnt,sums[p]);
            }
            s2.push(j);
          
        }



  while(!s2.empty()){
                int p=s2.top();
                s2.pop();
                int r=m-1;
                sums[p]+=(r-p-1)*(height[p]);
                                printf("%d %d %d %d\n",i,j,p,sums[p]);


                cnt=max(cnt,sums[p]);
            }



        /*for(int j=0;j<m;j++){
            cout<<sums[j]<<" ";
        }
        cout<<endl;
        for(int j=0;j<m;j++){
            cout<<height[j]<<" ";
        }
        cout<<endl;
    */
    }
    cout<<cnt<<endl;
}

发表于 2020-12-31 20:34:25 回复(0)

会飞的猪丶

#include<iostream>
#include<vector>
#include<stack>


using namespace std;
int res =0;

int GetMax(vector<int> &height){
    stack<int> st;
    int tmp_mx=0;
    int n=height.size();
    for(int i=0;i<height.size();i++){
        while(!st.empty()&&height[i]<=height[st.top()]){
            int x = height[st.top()];
            st.pop();
            int k= st.empty()?-1:st.top();
            tmp_mx=max(tmp_mx,(i-k-1)*x);
        }
        st.push(i);
    }
    while(!st.empty()){
         int x = height[st.top()];
         st.pop();
         int k= st.empty()?-1:st.top();
         tmp_mx=max(tmp_mx,(n-k-1)*x);
    }
    return tmp_mx;
}

int main(){
    int n,m;
    cin >> n >>m;
    vector<vector<int>> data(n,vector<int>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
           cin >> data[i][j];
        }
    vector<int> height(m,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(data[i][j]==1) height[j]+=1;
            else height[j]=0;
              // 构建出了height数组
        }    
        //返回每个数组的最大值，然后再取全局的最大值
            int mx=GetMax(height);
            res=max(res,mx);
    }
    cout << res ;
    return 0;
}

发表于 2020-08-25 14:22:29 回复(0)

秃头少女学Java

/* 一行一行分析 */
import java.util.Scanner;
import java.util.Stack;

public class Main{

    public static int findMaxFize(int[][] arr){
        if(arr == null || arr.length == 0 || arr[0].length == 0) return 0;
        int maxArea = 0;
        int[] h = new int[arr[0].length];
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr[0].length; j++){
                h[j] = arr[i][j] == 0 ? 0 : h[j]+1;
            }
            maxArea = Math.max(maxArea, maxRecFromBottom(h));
        }
        return maxArea;
    }

    public static int maxRecFromBottom(int[] height){
        if(height == null || height.length == 0) return 0;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < height.length; i++){
            while(!stack.isEmpty() && height[i] <= height[stack.peek()]){
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                int curArea = (i - k - 1) * height[j];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (height.length - k - 1) * height[j];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++)
                arr[i][j] = sc.nextInt();
        }
        int res = findMaxFize(arr);
        System.out.println(res);
    }
}

发表于 2020-06-14 13:05:10 回复(0)

我的小鱼你醒了

求输入的矩阵中的最大子矩阵，基本思路是，以每行作为矩阵的底边，分别计算最大矩阵。在算最大矩阵时，暴力遍历会超时，通过单调栈降低复杂度。即将其视为直方图，求最大矩阵，直方图用数组保存，一行行更新，遍历直方图，比栈顶大，说明栈顶元素还不能计算其矩阵面积，将该数放入栈，否则，计算栈顶的最大面积。时间复杂度O(NM)。

import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int l, r;
    String[] lr = sc.nextLine().split(" ");
    l = Integer.valueOf(lr[0]);
    r = Integer.valueOf(lr[1]);
    int[] hist = new int[r];
    Stack<Integer> sta = new Stack<>();
    int max = 0;
    int tmp = 0;
    int tmp2 = 0;
    for(int i=0; i<l; i++) {
        //更新直方图
        String[] str = sc.nextLine().split(" ");
        for(int j=0; j<r; j++) {
            hist[j] = Integer.valueOf(str[j]) == 1 ? hist[j]+1 : 0;
        }
        //找最大矩形,单调栈
//         sta.clear();
        for(int j=0; j<r; j++) {
            //开始计算每个矩形
            while(!sta.isEmpty() && hist[j] < hist[sta.peek()]) {
                tmp = sta.pop();
                if(sta.isEmpty())
                    tmp2 = hist[tmp] * j;
                else
                    tmp2 = hist[tmp] * (j - sta.peek() - 1);
                max = max > tmp2 ? max : tmp2;
            }
            sta.add(j);
        }
        while(!sta.isEmpty()) {
             tmp = sta.pop();
             if(sta.isEmpty())
                 tmp2 = hist[tmp] * r;
             else
                 tmp2 = hist[tmp] * (r - sta.peek() - 1);
             max = max > tmp2 ? max : tmp2;
        }
    }
    System.out.println(max);
    sc.close();
}

}

发表于 2020-02-02 23:50:15 回复(0)

星风雪宇

#include<iostream>
#include<vector>
using namespace std;
int getmaxlen(int* height,int m)
{
    vector<int> v1;
    int max_area=0;
    int max_area_temp=0;
    for(int i=0;i<m;i++)
    {
        while(!v1.empty()&&height[v1[v1.size()-1]]>height[i])
        {
            max_area_temp=height[v1[v1.size()-1]]*(i-v1[v1.size()-2]-1); 
            if(max_area_temp>max_area) max_area=max_area_temp;
            v1.pop_back();
        }
        v1.push_back(i);
    }
    return max_area;
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int** matrix=new int*[n];
        for(int i=0;i<n;i++)    matrix[i]=new int[m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                cin>>matrix[i][j];
            }
        int* height=new int[m]{};
        int max_len=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
               if(matrix[i][j]==1) height[j]++;
               else height[j]=0;
            }
            int len=getmaxlen(height,m);
            if(len>max_len) max_len=len;
        }
        cout<<max_len<<endl;
    }
}

发表于 2019-09-19 10:58:40 回复(0)

Python

汤普森30

将矩阵变换成直方图，计算直方图中的最大矩形，算法复杂度O(N^2)，不知道是不是因为python的缘故，超时了。。。只能AC75%

N, M= list(map(int,input().split()))
histogram = []
for i in range(N):
    nums = list(map(int,input().split()))
    histogram.append(nums)    #原矩阵
for j in range(M):
    for i in range(1, N):
        if histogram[i][j] == 1:
            histogram[i][j] += histogram[i-1][j]    #构造直方图
# 函数: 计算直方图中的最大矩形
def maxRect(nums):
    stack = []
    maxArea = 0
    nums.append(0)
    for i in range(len(nums)):
        while len(stack)>0 and nums[stack[-1]] > nums[i]:
            H = nums[stack.pop()]
            sidx = -1
            if len(stack)>0:
                sidx = stack[-1]
            area = H * (i-sidx-1)
            maxArea = max(maxArea, area)
        stack.append(i)
    return maxArea
 
maxR = 0
for i in range(N):
    nums = histogram[i]
    maxR = max(maxR, maxRect(nums)) #计算每一行 直方图中的最大矩形   
print(maxR)

编辑于 2019-08-23 19:02:28 回复(0)

求最大子矩阵的大小

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题