Dada una array arr[] de tamaño N , la tarea es encontrar el número de subarreglos cuyo primer elemento no sea mayor que otros elementos del subarreglo.
Ejemplos:
Entrada : arr = {1, 2, 1}
Salida: 5
Explicación: Todos los subarreglos son: {1}, {1, 2}, {1, 2, 1}, {2}, {2, 1}, {1 }
Del subarreglo anterior, lo siguiente cumple la condición: {1}, {1, 2}, {1, 2, 1}, {2}, {1}Entrada: arr[] = {1, 3, 5, 2}
Salida: 8
Explicación: Tenemos los siguientes subarreglos que cumplen la condición:
{1}, {1, 3}, {1, 3, 5}, {1 , 3, 5, 2}, {3}, {3, 5}, {5}, {2}
Enfoque ingenuo: el enfoque ingenuo es ejecutar un ciclo anidado y encontrar todos los subarreglos con el primer elemento no más grande que los otros elementos en el subarreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all subarrays with first
// element not bigger than other elements
int countSubarrays(vector<int>& arr)
{
int n = arr.size();
// Cnt is initialised to n because
// atleast n subarrays will be there
// which is single element itself
int cnt = n;
// Two loops to find the
// ending of each subarrays
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Minimum element from
// [start+1, end] of each subarray
int mini_ele = *min_element(begin(arr) + i + 1,
begin(arr) + j + 1);
// Checking if minimum of
// elements from [start+1, end] is
// not smaller than start element
// updating the count of subarrays
if (mini_ele >= arr[i])
cnt++;
}
}
return cnt;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 3, 5, 2 };
// Function call
cout << countSubarrays(arr) << "\n";
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the minimum element in a given range
public static int min_element(int arr[], int left, int right)
{
int x = Integer.MAX_VALUE;
for(int i=left;i<right;i++)
{
x=Math.min(x,arr[i]);
}
return x;
}
// Function to find all subarrays with first
// element not bigger than other elements
public static int countSubarrays(int arr[])
{
int n = arr.length;
// Cnt is initialised to n because
// atleast n subarrays will be there
// which is single element itself
int cnt = n;
// Two loops to find the
// ending of each subarrays
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
// Minimum element from
// [start+1, end] of each subarray
int mini_ele = min_element(arr,i+1,j+1);
// Checking if minimum of
// elements from [start+1, end] is
// not smaller than start element
// updating the count of subarrays
if (mini_ele >= arr[i])
cnt++;
}
}
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1, 3, 5, 2};
// Function call
System.out.println(countSubarrays(arr) );
}
}
// This code is contributed by Aditya Patil
Python3
# Python3 code to implement the approach # Function to find all subarrays with first # element not bigger than other elements # Function to find the minimum element in a given range import sys def min_element(arr, left, right): x = sys.maxsize for i in range(left, right): x = min(arr[i], x) return x def countSubarrays(arr): n = len(arr) # Cnt is initialised to n because # atleast n subarrays will be there # which is single element itself cnt = n # Two loops to find the # ending of each subarrays for i in range(n): for j in range(i+1,n): # Minimum element from # [start+1, end] of each subarray mini_ele = min_element(arr ,i + 1, j + 1) # Checking if minimum of # elements from [start+1, end] is # not smaller than start element # updating the count of subarrays if (mini_ele >= arr[i]): cnt += 1 return cnt # Driver Code arr = [ 1, 3, 5, 2 ] # Function call print(countSubarrays(arr)) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find the minimum element in a given range
public static int min_element(int []arr, int left, int right)
{
int x = int.MaxValue;
for(int i=left;i<right;i++)
{
x=Math.Min(x,arr[i]);
}
return x;
}
// Function to find all subarrays with first
// element not bigger than other elements
public static int countSubarrays(int []arr)
{
int n = arr.Length;
// Cnt is initialised to n because
// atleast n subarrays will be there
// which is single element itself
int cnt = n;
// Two loops to find the
// ending of each subarrays
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
// Minimum element from
// [start+1, end] of each subarray
int mini_ele = min_element(arr,i+1,j+1);
// Checking if minimum of
// elements from [start+1, end] is
// not smaller than start element
// updating the count of subarrays
if (mini_ele >= arr[i])
cnt++;
}
}
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 3, 5, 2};
// Function call
Console.WriteLine(countSubarrays(arr) );
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript code to implement the approach
// Function to find all subarrays with first
// element not bigger than other elements
// Function to find the minimum element in a given range
function min_element(arr,left,right){
let x = Number.MAX_VALUE
for(let i=left;i<right;i++){
x = Math.min(arr[i],x)
}
return x
}
function countSubarrays(arr)
{
let n = arr.length
// Cnt is initialised to n because
// atleast n subarrays will be there
// which is single element itself
let cnt = n
// Two loops to find the
// ending of each subarrays
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// Minimum element from
// [start+1, end] of each subarray
let mini_ele = min_element(arr ,i + 1, j + 1);
// Checking if minimum of
// elements from [start+1, end] is
// not smaller than start element
// updating the count of subarrays
if (mini_ele >= arr[i])
cnt++;
}
}
return cnt;
}
// Driver Code
let arr = [ 1, 3, 5, 2 ];
// Function call
document.write(countSubarrays(arr),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
8
Complejidad de Tiempo : O(N 3 )
Espacio Auxiliar : O(1)
Enfoque eficiente: el enfoque eficiente se basa en el concepto de encontrar el siguiente elemento más pequeño a la derecha de un elemento. Para implementar este concepto se utiliza la pila . Siga los pasos que se mencionan a continuación:
- Usamos una pila monótona para obtener el índice del siguiente elemento más pequeño de la derecha porque queremos que el subarreglo con el primer elemento sea el elemento mínimo.
- El subarreglo total en el rango [i, j] que tiene i como índice inicial es (j – i).
- Calcule el siguiente índice más pequeño para cada índice i , agregue (ji) para cada uno de ellos y siga actualizando el recuento total de subarreglos válidos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all subarrays with first
// element not bigger than other elements
int countSubarrays(vector<int>& arr)
{
// Taking stack for find next smaller
// element to the right
stack<int> s;
int ans = 0;
int n = arr.size();
// Looping from right side because we next
// smallest to the right
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() and arr[s.top()] >= arr[i])
s.pop();
// The index of next smaller element
// starting from i'th index
int last = (s.empty() ? n : s.top());
// Adding the number of subarray which
// can be formed in the range [i, last]
ans += (last - i);
s.push(i);
}
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 3, 5, 2 };
// Function call
cout << countSubarrays(arr) << "\n";
return 0;
}
Java
// JAVA code to implement the approach
import java.util.*;
class GFG {
// Function to find all subarrays with first
// element not bigger than other elements
public static int countSubarrays(int arr[])
{
// Taking stack for find next smaller
// element to the right
Stack<Integer> s = new Stack<Integer>();
int ans = 0;
int n = arr.length;
// Looping from right side because we next
// smallest to the right
for (int i = n - 1; i >= 0; i--) {
while (s.empty() == false
&& arr[s.peek()] >= arr[i])
s.pop();
// The index of next smaller element
// starting from i'th index
int last = ((s.empty() == true) ? n : s.peek());
// Adding the number of subarray which
// can be formed in the range [i, last]
ans += (last - i);
s.push(i);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = new int[] { 1, 3, 5, 2 };
// Function call
System.out.println(countSubarrays(arr));
}
}
// This code is contributed by Taranpreet
Python3
# Python 3 code to implement the approach # Function to find all subarrays with first # element not bigger than other elements def countSubarrays(arr): # Taking stack for find next smaller # element to the right s = [] ans = 0 n = len(arr) # Looping from right side because we next # smallest to the right for i in range(n - 1, -1, -1): while (len(s) != 0 and arr[s[-1]] >= arr[i]): s.pop() # The index of next smaller element # starting from i'th index if (len(s) == 0): last = n else: last = s[-1] # Adding the number of subarray which # can be formed in the range [i, last] ans += (last - i) s.append(i) return ans # Driver Code if __name__ == "__main__": arr = [1, 3, 5, 2] # Function call print(countSubarrays(arr)) # This code is contributed by ukasp.
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find all subarrays with first
// element not bigger than other elements
public static int countSubarrays(List<int> arr)
{
// Taking stack for find next smaller
// element to the right
Stack<int> s = new Stack<int>();
int ans = 0;
int n = arr.Count;
// Looping from right side because we next
// smallest to the right
for (int i = n - 1 ; i >= 0 ; i--) {
while (s.Count > 0 && arr[s.Peek()] >= arr[i]){
s.Pop();
}
// The index of next smaller element
// starting from i'th index
int last = (s.Count == 0 ? n : s.Peek());
// Adding the number of subarray which
// can be formed in the range [i, last]
ans += (last - i);
s.Push(i);
}
return ans;
}
// Driver Code
public static void Main(string[] args){
List<int> arr = new List<int>{
1, 3, 5, 2
};
// Function call
Console.Write(countSubarrays(arr));
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript code to implement the approach
// Function to find all subarrays with first
// element not bigger than other elements
const countSubarrays = (arr) => {
// Taking stack for find next smaller
// element to the right
let s = [];
let ans = 0;
let n = arr.length;
// Looping from right side because we next
// smallest to the right
for (let i = n - 1; i >= 0; i--)
{
while (s.length != 0 && arr[s[s.length - 1]] >= arr[i])
s.pop();
// The index of next smaller element
// starting from i'th index
let last = (s.length == 0 ? n : s[s.length - 1]);
// Adding the number of subarray which
// can be formed in the range [i, last]
ans += (last - i);
s.push(i);
}
return ans;
}
// Driver Code
let arr = [1, 3, 5, 2];
// Function call
document.write(countSubarrays(arr));
// This code is contributed by rakeshsahni
</script>
Producción
8
Tiempo Complejidad : 
Espacio Auxiliar: 