Dada una array N * M mat[][] , la tarea es encontrar la subarray rectangular más grande en área tal que cada columna y cada fila de la subarray sea estrictamente creciente.
Ejemplos:
Entrada: mat[][] =
{{1, 2, 3},
{4, 5, 6},
{1, 2, 3}}
Salida: 6
La subarray más grande será {{1, 2, 3} , {4, 5, 6}}.
Número de elementos en esta subarray = 6.Entrada: mat[][] =
{{1, 2, 3},
{4, 5, 3},
{1, 2, 3}}
Salida: 4
La subarray más grande será
{{1, 2}, {4, 5}}
Enfoque: Hay muchos enfoques para resolver este problema que van desde O(N 3 * M 3 ) hasta O(N * M). En este artículo, se discutirá un enfoque con complejidad de tiempo O(N * M) utilizando una pila .
Antes de continuar, se recomienda resolver esto. problema.
Tratemos de comprender el enfoque en términos generales, luego se discutirá el algoritmo. Para cada columna de la array, intente encontrar la subarray más grande ordenada por filas y columnas que tenga el borde izquierdo en esta columna. Para realizar lo mismo, cree una array pre[][] donde pre[i][j] almacenará la longitud del subarreglo creciente más largo a partir del índice j del arreglo arr[i] .
Ahora, usando esta array, para cada columna j , encuentre la longitud de la array ordenada por filas y columnas más larga. Para procesar una columna, se requerirán todos los subsegmentos crecientes de la array pre[][j] . Lo mismo se puede encontrar usando el puntero de dos puntos.técnica. En cada uno de estos subsegmentos, simplemente encuentre el área más grande debajo del histograma considerando los subsegmentos crecientes por filas como barras.
- Cree una array de suma de prefijos para cada fila ‘i’, que almacena la longitud de la sub-array creciente más grande que termina en cada columna ‘j’ de esa fila.
- Una vez que tenemos esta array, para cada columna ‘j’.
- Inicializar ‘i’ es igual a 0.
- Ejecute un ciclo en ‘i’ mientras ‘i’ es menor que ‘N’
- Inicializar ‘k’ es igual a i+1.
- mientras que k es menor que N y arr[k][j] es mayor que arr[k-1][j], incrementa k.
- Aplique el problema del histograma en el subconjunto pre[i][j] a pre[k-1][j], para encontrar el área más grande debajo de él. Llamemos a este valor ‘V’. Actualice la respuesta final como ans = max (ans, val).
- Actualizar ‘i’ es igual a k-1.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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 required 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;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to return the largest
// area under a histogram
static int histo(ArrayList<Integer> q)
{
// Stack
Stack<Integer> q1 = new Stack<Integer>();
// Length of the vector
int n = q.size();
// Function to store the next smaller
// and previous smaller index
int[] pre_smaller = new int[q.size()];
int[] next_smaller = new int[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() > 0 && q.get(q1.peek()) > q.get(i))
{
next_smaller[q1.peek()] = i;
q1.pop();
}
q1.push(i);
}
// Finding the previous smaller element
while (q1.size() > 0)
{
q1.pop();
}
for (int i = n - 1; i >= 0; i--)
{
while (q1.size() > 0 && q.get(q1.peek()) > q.get(i))
{
pre_smaller[q1.peek()] = 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 = Math.max(ans, (next_smaller[i] -
pre_smaller[i] - 1) *
q.get(i));
}
// Returning the final answer
return ans;
}
// Function to return the largest area
// for the required submatrix
static int findLargest(ArrayList<ArrayList<Integer>> arr)
{
// n and m store the number of
// rows and columns respectively
int n = arr.size();
int m = arr.get(0).size();
// To store the prefix_sum
int[][] pre=new int[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.get(i).get(j) > arr.get(i).get(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;
ArrayList<Integer> q = new ArrayList<Integer>();
q.add(pre[i][j]);
while (k < n && arr.get(k).get(0) > arr.get(k - 1).get(0))
{
q.add(pre[k][j]);
k++;
}
// Applying the largest area
// under the histogram
ans = Math.max(ans, histo(q));
i = k - 1;
}
}
// Return the final answer
return ans;
}
// Driver code
public static void main (String[] args)
{
ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
arr.add(new ArrayList<Integer>(Arrays.asList(1, 2, 3 )));
arr.add(new ArrayList<Integer>(Arrays.asList(4, 5, 6 )));
arr.add(new ArrayList<Integer>(Arrays.asList(1, 2, 3 )));
System.out.println(findLargest(arr));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 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 required 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
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return the largest
// area under a histogram
static int histo(List<int> q)
{
// Stack
Stack<int> q1 = new Stack<int>();
// Length of the vector
int n = q.Count;
// Function to store the next smaller
// and previous smaller index
int[] pre_smaller = new int[q.Count];
int[] next_smaller = new int[q.Count];
// 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.Count > 0 && q[q1.Peek()] > q[i])
{
next_smaller[q1.Peek()] = i;
q1.Pop();
}
q1.Push(i);
}
// Finding the previous smaller element
while (q1.Count > 0)
{
q1.Pop();
}
for(int i = n - 1; i >= 0; i--)
{
while (q1.Count > 0 && q[q1.Peek()] > q[i])
{
pre_smaller[q1.Peek()] = 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 = Math.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 required submatrix
static int findLargest(List<List<int>> arr)
{
// n and m store the number of
// rows and columns respectively
int n = arr.Count;
int m = arr[0].Count;
// To store the prefix_sum
int[,] pre = new int[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;
List<int> q = new List<int>();
q.Add(pre[i, j]);
while(k < n && arr[k][0] > arr[k - 1][0])
{
q.Add(pre[k, j]);
k++;
}
// Applying the largest area
// under the histogram
ans = Math.Max(ans, histo(q));
i = k - 1;
}
}
// Return the final answer
return ans;
}
// Driver code
static public void Main()
{
List<List<int>> arr = new List<List<int>>();
arr.Add(new List<int>(){1, 2, 3});
arr.Add(new List<int>(){4, 5, 6 });
arr.Add(new List<int>(){1, 2, 3});
Console.WriteLine(findLargest(arr));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation of the approach
// Function to return the largest
// area under a histogram
function histo(q)
{
// Stack
let q1 = [];
// Length of the vector
let n = q.length;
// Function to store the next smaller
// and previous smaller index
let pre_smaller = new Array(q.length);
let next_smaller = new Array(q.length);
// Finding the next smaller
for (let i = 0; i < n; i++)
{
pre_smaller[i] = -1;
next_smaller[i] = n;
}
for (let i = 0; i < n; i++)
{
while (q1.length > 0 && q[q1[q1.length-1]] > q[i])
{
next_smaller[q1[q1.length-1]] = i;
q1.pop();
}
q1.push(i);
}
// Finding the previous smaller element
while (q1.length > 0)
{
q1.pop();
}
for (let i = n - 1; i >= 0; i--)
{
while (q1.length > 0 && q[q1[q1.length-1]] > q[i])
{
pre_smaller[q1[q1.length-1]] = i;
q1.pop();
}
q1.push(i);
}
// To store the final answer
let ans = 0;
// Finding the final answer
for (let i = 0; i < n; i++)
{
ans = Math.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 required submatrix
function findLargest(arr)
{
// n and m store the number of
// rows and columns respectively
let n = arr.length;
let m = arr[0].length;
// To store the prefix_sum
let pre=new Array(n);
for(let i=0;i<n;i++)
{
pre[i]=new Array(m);
for(let j=0;j<m;j++)
{
pre[i][j]=0;
}
}
// To store the final answer
let ans = 0;
// Loop to create the prefix-sum
// using two pointers
for (let i = 0; i < n; i++)
{
for (let 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 (let j = 0; j < m; j++)
{
// Find the largest row-wise sorted arrays
for (let i = 0; i < n; i++)
{
let k = i + 1;
let q = [];
q.push(pre[i][j]);
while (k < n && arr[k][0] > arr[k - 1][0])
{
q.push(pre[k][j]);
k++;
}
// Applying the largest area
// under the histogram
ans = Math.max(ans, histo(q));
i = k - 1;
}
}
// Return the final answer
return ans;
}
// Driver code
let arr=[[1, 2, 3],[4, 5, 6 ],[1, 2, 3]];
document.write(findLargest(arr));
// This code is contributed by patel2127
</script>
Producción:
6
Complejidad de tiempo : O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces.
Espacio auxiliar : O(N*N), ya que estamos usando espacio adicional para la array.
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA