Dada una array height[] que representa la altura de N personas de pie en una fila. Una persona i puede ver a una persona j si altura[j] < altura[i] y no hay ninguna persona k parada entre ellos de tal forma que altura[j] ≥ altura[i] . Encuentra el número máximo de personas que una persona puede ver.
Nota: Una persona puede ver a cualquier otra persona independientemente de si están de pie delante o detrás de él.
Ejemplos:
Entrada: alturas[] = {6, 2, 5, 4, 5, 1, 6}.
Salida: 6
Explicación:
La persona 1 (altura = 6) puede ver a otras cinco personas en las siguientes posiciones (2, 3, 4, 5. 6) además de él mismo, es decir, un total de 6. La persona 2 (altura: 2) solo puede
ver él mismo.
La persona 3 (altura = 5) puede ver a las personas en 2.ª, 3.ª y 4.ª persona.
Solo la Persona 4 (altura = 4) puede verse a sí misma.
La persona 5 (altura = 5) puede ver a las personas 4, 5 y 6.
La persona 6 (altura = 1) solo puede verse a sí misma.
La persona 7 (altura = 6) puede ver a las personas 2, 3, 4, 5, 6 y 7.
Un máximo de seis personas pueden ser vistos por Persona 1, 7.
Entrada : alturas[] = {1, 3, 6, 4}
Salida : 3
Enfoque ingenuo: una solución simple es iterar a través de la array dada y para cada idx en la fila:
- Mantenga un puntero izquierdo (leftptr ) que apunta a idx-1 y un puntero derecho (rightptr) que apunta a idx+1 .
- Mueva el puntero izquierdo en la dirección izquierda hasta que encuentre una persona cuya altura sea mayor o igual que height[idx] .
- Mueva el puntero derecho en la dirección correcta hasta que encuentre una persona cuya altura sea mayor o igual que la altura [idx] .
- La diferencia entre los índices del puntero derecho e izquierdo nos da el número de personas que la i-ésima persona puede ver y actualizar el Ans como max(Ans, rightptr – leftptr-1) .
A continuación se muestra la implementación de la idea anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the leftmost index
// of the person whose height is
// greater the height of person idx.
int leftindex(vector<int> heights,
int idx, int n)
{
int h = heights[idx];
for (int i = idx - 1; i >= 0; i--) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his left
return -1;
}
// Function to find the rightmost index
// of the person whose height is
// greater the height of person idx.
int rightindex(vector<int> heights,
int idx, int n)
{
int h = heights[idx];
for (int i = idx + 1; i < n; i++) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his right
return n;
}
// Function to find maximum number of people
// a person can see
int max_people(vector<int> heights, int n)
{
// Ans stores the maximum of people
// a person can see
int ans = 0;
for (int i = 0; i < n; i++) {
// Leftptr stores the leftmost index
// of the person which
// the current person cannot see
int leftptr
= leftindex(heights, i, n);
// Rightptr stores the rightmost index
// of the person which
// the current person cannot see
int rightptr
= rightindex(heights, i, n);
// Maximum number of people
// a person can see
ans = max(ans,
rightptr - leftptr - 1);
}
return ans;
}
// Driver code
int main()
{
int N = 7;
vector<int> heights{ 6, 2, 5, 4, 5, 1, 6 };
// Function call
cout << max_people(heights, N) << endl;
return 0;
}
Java
// JAVA code to implement the above approach
import java.util.*;
class GFG
{
// Function to find the leftmost index
// of the person whose height is
// greater the height of person idx.
public static int leftindex(int[] heights, int idx,
int n)
{
int h = heights[idx];
for (int i = idx - 1; i >= 0; i--) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his left
return -1;
}
// Function to find the rightmost index
// of the person whose height is
// greater the height of person idx.
public static int rightindex(int[] heights, int idx,
int n)
{
int h = heights[idx];
for (int i = idx + 1; i < n; i++) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his right
return n;
}
// Function to find maximum number of people
// a person can see
public static int max_people(int[] heights, int n)
{
// Ans stores the maximum of people
// a person can see
int ans = 0;
for (int i = 0; i < n; i++) {
// Leftptr stores the leftmost index
// of the person which
// the current person cannot see
int leftptr = leftindex(heights, i, n);
// Rightptr stores the rightmost index
// of the person which
// the current person cannot see
int rightptr = rightindex(heights, i, n);
// Maximum number of people
// a person can see
ans = Math.max(ans, rightptr - leftptr - 1);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 7;
int[] heights = new int[] { 6, 2, 5, 4, 5, 1, 6 };
// Function call
System.out.println(max_people(heights, N));
}
}
// This code is contributed by Taranpreet
Python3
# Python code to implement the above approach # Function to find the leftmost index # of the person whose height is # greater the height of person idx. def leftindex(heights, idx, n): h = heights[idx] for i in range(idx - 1, -1, -1): # If height of person i is # greater than or equal to # current person of height h # then the current person(idx) # cannot see him if heights[i] >= h: return i # If a person can see all other people # who are standing on his left return -1 # Function to find the rightmost index # of the person whose height is # greater the height of person idx. def rightindex(heights, idx, n): h = heights[idx] for i in range(idx + 1, n): # If height of person i is # greater than or equal to # current person of height h # then the current person(idx) # cannot see him if (heights[i] >= h): return i # If a person can see all other people # who are standing on his right return n # Function to find maximum number of people # a person can see def max_people(heights, n): # Ans stores the maximum of people # a person can see ans = 0 for i in range(n): # Leftptr stores the leftmost index # of the person which # the current person cannot see leftptr = leftindex(heights, i, n) # Rightptr stores the rightmost index # of the person which # the current person cannot see rightptr = rightindex(heights, i, n) # Maximum number of people # a person can see ans = max(ans, rightptr - leftptr - 1) return ans # Driver code N = 7 heights=[6, 2, 5, 4, 5, 1, 6] # Function call print(max_people(heights, N)) # This code is contributed by rohitsingh07052.
C#
// C# code to implement the above approach
using System;
class GFG
{
// Function to find the leftmost index
// of the person whose height is
// greater the height of person idx.
static int leftindex(int[] heights, int idx,
int n)
{
int h = heights[idx];
for (int i = idx - 1; i >= 0; i--) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his left
return -1;
}
// Function to find the rightmost index
// of the person whose height is
// greater the height of person idx.
static int rightindex(int[] heights, int idx,
int n)
{
int h = heights[idx];
for (int i = idx + 1; i < n; i++) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his right
return n;
}
// Function to find maximum number of people
// a person can see
static int max_people(int[] heights, int n)
{
// Ans stores the maximum of people
// a person can see
int ans = 0;
for (int i = 0; i < n; i++) {
// Leftptr stores the leftmost index
// of the person which
// the current person cannot see
int leftptr = leftindex(heights, i, n);
// Rightptr stores the rightmost index
// of the person which
// the current person cannot see
int rightptr = rightindex(heights, i, n);
// Maximum number of people
// a person can see
ans = Math.Max(ans, rightptr - leftptr - 1);
}
return ans;
}
// Driver code
public static void Main()
{
int N = 7;
int[] heights = new int[] { 6, 2, 5, 4, 5, 1, 6 };
// Function call
Console.WriteLine(max_people(heights, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code to implement the above approach
// Function to find the leftmost index
// of the person whose height is
// greater the height of person idx.
const leftindex = (heights, idx, n) => {
let h = heights[idx];
for (let i = idx - 1; i >= 0; i--) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his left
return -1;
}
// Function to find the rightmost index
// of the person whose height is
// greater the height of person idx.
const rightindex = (heights, idx, n) => {
let h = heights[idx];
for (let i = idx + 1; i < n; i++) {
// If height of person i is
// greater than or equal to
// current person of height h
// then the current person(idx)
// cannot see him
if (heights[i] >= h)
return i;
}
// If a person can see all other people
// who are standing on his right
return n;
}
// Function to find maximum number of people
// a person can see
const max_people = (heights, n) => {
// Ans stores the maximum of people
// a person can see
let ans = 0;
for (let i = 0; i < n; i++) {
// Leftptr stores the leftmost index
// of the person which
// the current person cannot see
let leftptr
= leftindex(heights, i, n);
// Rightptr stores the rightmost index
// of the person which
// the current person cannot see
let rightptr
= rightindex(heights, i, n);
// Maximum number of people
// a person can see
ans = Math.max(ans,
rightptr - leftptr - 1);
}
return ans;
}
// Driver code
let N = 7;
let heights = [6, 2, 5, 4, 5, 1, 6];
// Function call
document.write(max_people(heights, N));
// This code is contributed by rakeshsahni
</script>
Producción
6
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: este problema se puede resolver usando pilas . Para cada persona en la fila, estamos tratando de encontrar el índice de la siguiente persona más alta a la derecha y la siguiente persona más alta a la izquierda .
- Cree una array r_heights de tamaño N para almacenar el índice de la siguiente persona mayor (derecha).
- Para encontrar la posición de la siguiente persona mayor a la derecha:
- empuja el último índice de la array a la pila.
- Para cada índice que va de N-1 a 0 :
- siga extrayendo los índices de la pila hasta que encuentre un índice cuya altura sea mayor o igual que la altura de la persona actual o hasta que la pila esté vacía.
- Si la pila no está vacía, actualice el valor de r_heights[i] para que coincida con la parte superior de la pila, de lo contrario, r_heights[i]=N.
- Empuje el índice actual a la pila.
- Iterar de 0 a N para encontrar el índice de la siguiente persona mayor en el lado izquierdo para cada persona en la fila.
- Para cada persona en la fila, el número de personas que puede ver es r_heigths[i]-l_heights[i]-1 . Actualice Ans como max (Ans, r_heigths[i]-l_heigths[i]-1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to store the index
// of next taller person on left
void leftindex(vector<int> heights,
vector<int>& l_heights,
int n)
{
stack<int> st;
for (int i = 0; i < n; i++) {
// While the top value of the stack
// is lesser than the
// current person's height
while (st.empty() == false
&& heights[st.top()]
< heights[i])
st.pop();
// If the stack is empty
l_heights[i]
= (st.empty() == false)
? st.top()
: (-1);
st.push(i);
}
return;
}
// Function to store the index of
// next taller person on right
void rightindex(vector<int>& heights,
vector<int>& r_heights,
int n)
{
// Stack to store the next
// taller person on its right
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
// If the top value of the stack
// is lesser than the current height
while (st.empty() == false
&& heights[st.top()]
< heights[i])
st.pop();
// If the stack is empty
r_heights[i]
= (st.empty() == false)
? st.top()
: n;
st.push(i);
}
return;
}
// Function to find the maximum number
// of people a person can see
int max_people(vector<int> heights, int n)
{
// To store the answer
int ans = 0;
vector<int> r_heights(n), l_heights(n);
leftindex(heights, l_heights, n);
rightindex(heights, r_heights, n);
for (int i = 0; i < n; i++) {
// Contains the leftmost index
// of the person which
// current person cannot see
int l_index = l_heights[i];
// Contains the rightmost index
// of the person which
// the current person cannot see
int r_index = r_heights[i];
// Calculate the maximum answer
ans = max(ans, r_index - l_index - 1);
}
return ans;
}
// Driver code
int main()
{
int N = 7;
vector<int> heights{ 6, 2, 5, 4, 5, 1, 6 };
// Function call
cout << max_people(heights, N) << endl;
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to store the index
// of next taller person on left
public static void leftindex(int heights[],
int l_heights[], int n)
{
Stack<Integer> st = new Stack<Integer>();
for (int i = 0; i < n; i++) {
// While the top value of the stack
// is lesser than the
// current person's height
while (st.empty() == false
&& heights[st.peek()] < heights[i])
st.pop();
// If the stack is empty
l_heights[i]
= (st.empty() == false) ? st.peek() : (-1);
st.push(i);
}
return;
}
// Function to store the index of
// next taller person on right
public static void rightindex(int heights[],
int r_heights[], int n)
{
// Stack to store the next
// taller person on its right
Stack<Integer> st = new Stack<Integer>();
for (int i = n - 1; i >= 0; i--) {
// If the top value of the stack
// is lesser than the current height
while (st.empty() == false
&& heights[st.peek()] < heights[i])
st.pop();
// If the stack is empty
r_heights[i]
= (st.empty() == false) ? st.peek() : n;
st.push(i);
}
return;
}
// Function to find the maximum number
// of people a person can see
public static int max_people(int heights[], int n)
{
// To store the answer
int ans = 0;
int r_heights[] = new int[n];
int l_heights[] = new int[n];
leftindex(heights, l_heights, n);
rightindex(heights, r_heights, n);
for (int i = 0; i < n; i++) {
// Contains the leftmost index
// of the person which
// current person cannot see
int l_index = l_heights[i];
// Contains the rightmost index
// of the person which
// the current person cannot see
int r_index = r_heights[i];
// Calculate the maximum answer
ans = Math.max(ans, r_index - l_index - 1);
}
return ans;
}
public static void main(String[] args)
{
int N = 7;
int heights[] = { 6, 2, 5, 4, 5, 1, 6 };
// Function call
System.out.println(max_people(heights, N));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code to implement the above approach # Function to store the index # of next taller person on left def leftindex(heights, l_heights, n): st = [] for i in range(n): # While the top value of the stack # is lesser than the # current person's height while (st != [] and heights[st[-1]] < heights[i]): st.pop() # If the stack is empty if st: l_heights[i] = st[-1] else: l_heights[i] = -1 st.append(i) return l_heights # Function to store the index of # next taller person on right def rightindex(heights, r_heights, n): # Stack to store the next # taller person on its right st = [] for i in range(n - 1, -1, -1): # If the top value of the stack # is lesser than the current height while (st != [] and heights[st[-1]] < heights[i]): st.pop() # If the stack is empty if st: r_heights[i] = st[-1] else: r_heights[i] = n st.append(i) return r_heights # Function to find the maximum number # of people a person can see def max_people( heights, n): # To store the answer ans = 0 r_heights=[0 for i in range(n)] l_heights= [0 for i in range(n)] l_heights = leftindex(heights, l_heights, n) r_heights = rightindex(heights, r_heights, n) for i in range(n): # Contains the leftmost index # of the person which # current person cannot see l_index = l_heights[i] # Contains the rightmost index # of the person which # the current person cannot see r_index = r_heights[i] # Calculate the maximum answer ans = max(ans, r_index - l_index - 1) return ans # Driver code N = 7 heights = [6, 2, 5, 4, 5, 1, 6 ] # Function call print(max_people(heights, N)) # This code is contributed by rohitsingh07052.
Javascript
<script>
// Javascript code to implement the above approach
// Function to store the index
// of next taller person on left
function leftindex(heights, l_heights, n){
let st = []
for(let i=0;i<n;i++){
// While the top value of the stack
// is lesser than the
// current person's height
while (st != [] && heights[st[st.length-1]] < heights[i])
st.pop()
// If the stack is empty
if(st.length > 0)
l_heights[i] = st[st.length-1]
else
l_heights[i] = -1
st.push(i)
}
return l_heights
}
// Function to store the index of
// next taller person on right
function rightindex(heights, r_heights, n){
// Stack to store the next
// taller person on its right
st = []
for(let i= n-1;i>=0;i--){
// If the top value of the stack
// is lesser than the current height
while (st != [] && heights[st[st.length-1]] < heights[i])
st.pop()
// If the stack is empty
if(st.length > 0)
r_heights[i] = st[st.length-1]
else
r_heights[i] = n
st.push(i)
}
return r_heights
}
// Function to find the maximum number
// of people a person can see
function max_people( heights, n){
// To store the answer
let ans = 0
let r_heights=new Array(n).fill(0)
let l_heights= new Array(n).fill(0)
l_heights = leftindex(heights, l_heights, n)
r_heights = rightindex(heights, r_heights, n)
for(let i=0;i<n;i++){
// Contains the leftmost index
// of the person which
// current person cannot see
let l_index = l_heights[i]
// Contains the rightmost index
// of the person which
// the current person cannot see
let r_index = r_heights[i]
// Calculate the maximum answer
ans = Math.max(ans, r_index - l_index - 1)
}
return ans
}
// Driver code
let N = 7
let heights = [6, 2, 5, 4, 5, 1, 6 ]
// Function call
document.write(max_people(heights, N))
// This code is contributed by shinjanpatra
</script>
Producción
6
Complejidad temporal : O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por mallupallisrividyareddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA