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

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

本文概述

给定一个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
                 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 the final answer
     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

时间复杂度：O(N^2)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: