算法题（最大的按行和按列排序的子矩阵） _数据结构

本文概述

CPP
python

给定一个N * M矩阵mat[][]，任务是找到面积最大的矩形子矩阵，使子矩阵的每列每行都是严格递增的。
例子：

输入：mat [] [] = {{1, 2, 3}, {4, 5, 6}, {1, 2, 3}}
输出：6
最大的子矩阵将是{{1, 2, 3} , {4, 5, 6}}。此子矩阵中的元素数=6。
输入：mat [] [] = {{1, 2, 3}, {4, 5, 3}, {1, 2, 3}}
输出：4
最大的子-matrix将为{{1, 2}, {4, 5}}

方法:有许多方法来解决这个问题，从O(N^3 * M^3)到O(N * M).在这篇文章中，将讨论一个O(N * M)时间复杂度的方法使用堆栈。
让我们试着从广义上理解这种方法，然后讨论算法。对于矩阵的每一列，试着找到左边在这一列的最大的行排序和列排序子矩阵。为了执行同样的操作，创建一个矩阵pre[][]，其中pre[i][j]将存储从数组arr[i]的索引j开始最长的递增子数组的长度。
现在使用这个矩阵，对于每一列j，求出最长的行排序和列排序数组的长度。要处理一列，需要数组pre[][j]中所有不断增加的子段。使用两个指针技术也可以找到相同的结果。在每一个子区段中，只需找到直方图下最大的区域，将逐行递增的子区段视为条形图。

为每行" 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); }//To store the final answer int ans = 0; //Finding the final answer for ( int i = 0; i < n; i++) ans = max(ans, (next_smaller[i] - pre_smaller[i] - 1) * q[i]); //Returning the final answer 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]; //To store the final answer 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 the final answer 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# Finding the final answer for i in range (n): ans = max (ans, (next_smaller[i] - pre_smaller[i] - 1 ) * q[i])# Returning the final answer 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 continueif (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 the final answer return ans# Driver codearr = [ [ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 1 , 2 , 3 ] ]print (findLargest(arr))# This code is contributed by mohit kumar 29

输出如下：