# 算法题：最大的按行和按列排序的子矩阵

2021年4月30日15:33:20 发表评论 990 次浏览

## 本文概述

• 为每行" i"创建一个前缀和数组, 该数组存储以该行的每一列" j"结尾的最大递增子数组的长度。
• 一旦有了这个数组, 对于每一列" j"。
• 初始化" i"等于0。
• 在" i"小于" N"时在" i"上循环
• 初始化" k"等于i + 1。
• 当k小于N且arr [k] [j]大于arr [k-1] [j]时, 递增k。
• 在子数组pre [i] [j]到pre [k-1] [j]上应用直方图问题, 以找到其下的最大面积。让我们将此值称为" V"。将最终答案更新为ans = max(ans, val)。
• 更新" i"等于k-1。

## CPP

``````//C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

//Function to return the largest
//area under a histogram
int histo(vector<int> q)
{

//Stack
stack<int> q1;

//Length of the vector
int n = q.size();

//Function to store the next smaller
//and previous smaller index
int pre_smaller[q.size()];
int next_smaller[q.size()];

//Finding the next smaller
for ( int i = 0; i <n; i++)
pre_smaller[i] = -1, next_smaller[i] = n;
for ( int i = 0; i <n; i++) {
while (q1.size() and q[q1.top()]> q[i]) {
next_smaller[q1.top()] = i;
q1.pop();
}
q1.push(i);
}

//Finding the previous smaller element
while (q1.size())
q1.pop();
for ( int i = n - 1; i>= 0; i--) {
while (q1.size() and q[q1.top()]> q[i]) {
pre_smaller[q1.top()] = i;
q1.pop();
}
q1.push(i);
}

int ans = 0;

for ( int i = 0; i <n; i++)
ans = max(ans, (next_smaller[i]
- pre_smaller[i] - 1)
* q[i]);

return ans;
}

//Function to return the largest area
//for the requried submatrix
int findLargest(vector<vector<int>> arr)
{
//n and m store the number of
//rows and columns respectively
int n = arr.size();
int m = arr[0].size();

//To store the prefix_sum
int pre[n][m];

int ans = 0;

//Loop to create the prefix-sum
//using two pointers
for ( int i = 0; i <n; i++)
for ( int j = 0; j <m; j++) {
if (j == 0) {
pre[i][j] = 1;
continue ;
}
if (arr[i][j]> arr[i][j - 1])
pre[i][j] = pre[i][j - 1] + 1;
else
pre[i][j] = 1;
}

//For each column run the loop
for ( int j = 0; j <m; j++) {

//Find the largest row-wise sorted arrays
for ( int i = 0; i <n; i++) {
int k = i + 1;
vector<int> q;
q.push_back(pre[i][j]);
while (k <n and arr[k]> arr[k - 1])
q.push_back(pre[k][j]), k++;

//Applying the largest area
//under the histogram
ans = max(ans, histo(q));
i = k - 1;
}
}

return ans;
}

//Driver code
int main()
{
vector<vector<int>> arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 1, 2, 3 } };

cout <<findLargest(arr);

return 0;
}``````

## python

``````# Pythono3 implementation of the approach

# Function to return the largest
# area under a histogram
def histo(q):

# Stack
q1 = []

# Length of the vector
n = len (q)

# Function to store the next smaller
# and previous smaller index
pre_smaller = [ 0 for i in range ( len (q))]
next_smaller = [ 0 for i in range ( len (q))]

# Finding the next smaller
for i in range (n):
pre_smaller[i] = - 1
next_smaller[i] = n
for i in range (n):
while ( len (q1)> 0 and q[q1[ - 1 ]]> q[i]):
next_smaller[q1[ - 1 ]] = i
del q1[ - 1 ]
q1.append(i)

# Finding the previous smaller element
while ( len (q1)> 0 ):
del q1[ - 1 ]

for i in range (n - 1 , - 1 , - 1 ):
while ( len (q1)> 0 and q[q1[ - 1 ]]> q[i]):
pre_smaller[q1[ - 1 ]] = i
del q1[ - 1 ]

q1.append(i)

# To store the final answer
ans = 0

for i in range (n):
ans = max (ans, (next_smaller[i] - pre_smaller[i] - 1 ) * q[i])

return ans

# Function to return the largest area
# for the requried submatrix
def findLargest(arr):

# n and m store the number of
# rows and columns respectively
n = len (arr)
m = len (arr[ 0 ])

# To store the prefix_sum
pre = [[ 0 for i in range (m)] for i in range (n)]

# To store the final answer
ans = 0

# Loop to create the prefix-sum
# using two pointers
for i in range (n):
for j in range (m):
if (j = = 0 ):
pre[i][j] = 1
continue

if (arr[i][j]> arr[i][j - 1 ]):
pre[i][j] = pre[i][j - 1 ] + 1
else :
pre[i][j] = 1

# For each column run the loop
for j in range (m):

# Find the largest row-wise sorted arrays
for i in range (n):
k = i + 1
q = []
q.append(pre[i][j])
while (k <n and arr[k]> arr[k - 1 ]):
q.append(pre[k][j])
k + = 1

# Applying the largest area
# under the histogram
ans = max (ans, histo(q))
i = k - 1

return ans

# Driver code

arr = [ [ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 1 , 2 , 3 ] ]

print (findLargest(arr))

# This code is contributed by mohit kumar 29``````

``6``