求最大子矩阵的大小

#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;
}

#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;
}

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));
    }
}

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)
}

今天吃我尸体,太难了

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)

#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;
}

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;
    }
}

#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;
}

#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;
}
  	

#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;
}

/* 一行一行分析 */
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);
    }
}

#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;
    }
}