Dada una array arr[] , la tarea es encontrar el recuento de subarreglos a partir del elemento actual que tiene un elemento mínimo como elemento actual en sí.
Ejemplos:
Entrada: arr[] = {2, 4, 2, 1, 3}
Salida: {3, 1, 1, 2, 1}
Explicación: Para el primer elemento podemos formar 3 subarreglos válidos con la condición dada
- 2 -> {2} , {2,4} , {2,4,2} = 3 subarreglos y así sucesivamente
- 4 -> {4} = 1 subarreglo
- 2 -> {2} = 1 subarreglo
- 1 -> {1} , {1, 3} = 2 subarreglos
- 3 -> {3} = 1 subarreglo
Entrada: arr[] = {1, 4, 2, 5, 3}
Salida: {5, 1, 3, 1, 1}
Solución ingenua: el enfoque ingenuo gira en torno a la idea de que:
- Si no se encuentra el elemento más pequeño, entonces cuenta de subarreglos = longitud del arreglo – índice actual
- Si se encuentra el elemento, entonces cuenta de subarreglos = índice del elemento más pequeño – índice actual
La tarea se puede resolver usando 2 bucles . El bucle exterior recoge todos los elementos uno por uno. El bucle interior busca el primer elemento más pequeño para el elemento elegido por el bucle exterior. Si se encuentra un elemento más pequeño, el índice de ese elemento , el índice actual, se almacena como el siguiente; de lo contrario, se almacena la longitud , el índice actual .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of subarrays
vector<int> countOfSubArray(vector<int> arr)
{
int next, i, j;
int n = arr.size();
vector<int> ans;
for (i = 0; i < n; i++) {
bool flag = false;
// If the next smaller element
// is not found then
// length - current index
// would be the answer
next = n - i;
for (j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
// If the next smaller
// element is found then
// the difference of indices
// will be the count
next = j - i;
ans.push_back(next);
flag = true;
break;
}
}
if (flag == false) {
ans.push_back(next);
}
}
return ans;
}
// Driver Code
int main()
{
vector<int> arr{ 1, 4, 2, 5, 3 };
vector<int> ans = countOfSubArray(arr);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
class GFG {
// Function to find the count of subarrays
static ArrayList<Integer> countOfSubArray(int[] arr) {
int next, i, j;
int n = arr.length;
ArrayList<Integer> ans = new ArrayList<Integer>();
for (i = 0; i < n; i++) {
boolean flag = false;
// If the next smaller element
// is not found then
// length - current index
// would be the answer
next = n - i;
for (j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
// If the next smaller
// element is found then
// the difference of indices
// will be the count
next = j - i;
ans.add(next);
flag = true;
break;
}
}
if (flag == false) {
ans.add(next);
}
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 1, 4, 2, 5, 3 };
ArrayList<Integer> ans = countOfSubArray(arr);
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i) + " ");
}
}
}
// This code is contributed by gfgking.
Python3
# Python code for the above approach # Function to find the count of subarrays def countOfSubArray(arr): n = len(arr) ans = [] for i in range(n): flag = 0 # If the next smaller element # is not found then # length - current index # would be the answer next = n - i for j in range(i + 1, n): if arr[i] > arr[j]: # If the next smaller # element is found then # the difference of indices # will be the count next = j - i ans.append(next) flag = 1 break if flag == 0: ans.append(next) return ans # Driver Code arr = [1, 4, 2, 5, 3] ans = countOfSubArray(arr) for i in range(len(ans)): print(ans[i], end = " ") # This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the count of subarrays
static List<int> countOfSubArray(int[] arr)
{
int next, i, j;
int n = arr.Length;
List<int> ans = new List<int>();
for (i = 0; i < n; i++) {
bool flag = false;
// If the next smaller element
// is not found then
// length - current index
// would be the answer
next = n - i;
for (j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
// If the next smaller
// element is found then
// the difference of indices
// will be the count
next = j - i;
ans.Add(next);
flag = true;
break;
}
}
if (flag == false) {
ans.Add(next);
}
}
return ans;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 4, 2, 5, 3 };
List<int> ans = countOfSubArray(arr);
for (int i = 0; i < ans.Count; i++) {
Console.Write(ans[i] + " ");
}
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the count of subarrays
const countOfSubArray = (arr) => {
let next, i, j;
let n = arr.length;
let ans = [];
for (i = 0; i < n; i++) {
let flag = false;
// If the next smaller element
// is not found then
// length - current index
// would be the answer
next = n - i;
for (j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
// If the next smaller
// element is found then
// the difference of indices
// will be the count
next = j - i;
ans.push(next);
flag = true;
break;
}
}
if (flag == false) {
ans.push(next);
}
}
return ans;
}
// Driver Code
let arr = [1, 4, 2, 5, 3];
let ans = countOfSubArray(arr);
for (let i = 0; i < ans.length; i++) {
document.write(`${ans[i]} `);
}
// This code is contributed by rakeshsahni
</script>
Producción
5 1 3 1 1
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(1)
Solución eficiente: este problema básicamente pide encontrar qué tan lejos está el índice actual del índice del siguiente número más pequeño al número en el índice actual. La forma más óptima de resolver este problema es haciendo uso de una pila .
Siga los pasos a continuación para resolver el problema:
- Itere sobre cada número de la array dada arr[] usando el índice actual.
- Si la pila está vacía, inserte el índice actual en la pila.
- Si la pila no está vacía, haga lo siguiente:
- Si el número en el índice actual es menor que el número del índice en la parte superior de la pila, empuje el índice actual.
- Si el número en el índice actual es mayor que el número del índice en la parte superior de la pila, actualice el recuento de subarreglos como el índice en la parte superior de la pila: índice actual
- Haga estallar la pila una vez que se haya actualizado el número de días en la lista de salida.
- Repita los pasos anteriores para todos los índices de la pila que sean mayores que el número del índice actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to determine how many count
// of subarrays are possible
// with each number
vector<int> countOfSubArray(vector<int> arr)
{
stack<int> st;
// To store the answer
vector<int> v;
int n = arr.size();
// Traverse all the numbers
for (int i = n - 1; i >= 0; i--) {
// Check if current index is the
// next smaller element of
// any previous indices
while (st.size() > 0
&& arr[st.top()] >= arr[i]) {
// Pop the element
st.pop();
}
if (st.size() == 0) {
v.push_back(n - i);
}
else {
v.push_back(st.top() - i);
}
// Push the current index
st.push(i);
}
// reverse the output
reverse(v.begin(), v.end());
return v;
}
// Driver Code
int main()
{
// Given numbers
vector<int> arr{ 1, 4, 2, 5, 3 };
// Function Call
vector<int> ans = countOfSubArray(arr);
// Printing the result
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to determine how many count
// of subarrays are possible
// with each number
static Vector<Integer> countOfSubArray(int[] arr)
{
Stack<Integer> st = new Stack<Integer>();
// To store the answer
Vector<Integer> v = new Vector<Integer>();
int n = arr.length;
// Traverse all the numbers
for (int i = n - 1; i >= 0; i--) {
// Check if current index is the
// next smaller element of
// any previous indices
while (st.size() > 0
&& arr[st.peek()] >= arr[i])
{
// Pop the element
st.pop();
}
if (st.size() == 0) {
v.add(n - i);
}
else {
v.add(st.peek() - i);
}
// Push the current index
st.add(i);
}
// reverse the output
Collections.reverse(v);
return v;
}
// Driver Code
public static void main(String[] args)
{
// Given numbers
int []arr ={ 1, 4, 2, 5, 3 };
// Function Call
Vector<Integer> ans = countOfSubArray(arr);
// Printing the result
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i)+ " ");
}
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for the above approach # Function to determine how many count # of subarrays are possible # with each number def countOfSubArray(arr): st = [] # To store the answer v = [] n = len(arr) # Traverse all the numbers for i in range(n - 1,-1,-1): # Check if current index is the # next smaller element of # any previous indices while len(st) > 0 and arr[st[len(st)-1]] >= arr[i] : # Pop the element st.pop() if (len(st) == 0): v.append(n - i) else: v.append(st[len(st) - 1]- i) # Push the current index st.append(i) # reverse the output v = v[::-1] return v # Driver Code # Given numbers arr = [ 1, 4, 2, 5, 3 ] # Function Call ans = countOfSubArray(arr) # Printing the result for i in range(len(ans)): print(ans[i],end = " ") # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to determine how many count
// of subarrays are possible
// with each number
static List<int> countOfSubArray(int[] arr)
{
Stack<int> st = new Stack<int>();
// To store the answer
List<int> v = new List<int>();
int n = arr.Length;
// Traverse all the numbers
for (int i = n - 1; i >= 0; i--) {
// Check if current index is the
// next smaller element of
// any previous indices
while (st.Count > 0
&& arr[st.Peek()] >= arr[i])
{
// Pop the element
st.Pop();
}
if (st.Count == 0) {
v.Add(n - i);
}
else {
v.Add(st.Peek() - i);
}
// Push the current index
st.Push(i);
}
// reverse the output
v.Reverse();
return v;
}
// Driver Code
public static void Main(String[] args)
{
// Given numbers
int []arr ={ 1, 4, 2, 5, 3 };
// Function Call
List<int> ans = countOfSubArray(arr);
// Printing the result
for (int i = 0; i < ans.Count; i++) {
Console.Write(ans[i]+ " ");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to determine how many count
// of subarrays are possible
// with each number
function countOfSubArray(arr)
{
let st = [];
// To store the answer
let v = [];
let n = arr.length;
// Traverse all the numbers
for (let i = n - 1; i >= 0; i--) {
// Check if current index is the
// next smaller element of
// any previous indices
while (st.length > 0
&& arr[st[st.length-1]] >= arr[i])
{
// Pop the element
st.pop();
}
if (st.length == 0) {
v.push(n - i);
}
else {
v.push(st[st.length - 1]- i);
}
// Push the current index
st.push(i);
}
// reverse the output
v.reverse();
return v;
}
// Driver Code
// Given numbers
let arr = [ 1, 4, 2, 5, 3 ];
// Function Call
let ans = countOfSubArray(arr);
// Printing the result
for (let i = 0; i < ans.length; i++) {
document.write(ans[i]," ");
}
// This code is contributed by shinjanpatra
</script>
Producción
5 1 3 1 1
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por prasanna1995 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA