Dada una string S que consta de N letras minúsculas únicas y una array arr[] de longitud N donde el carácter S[i] representa la bombilla y arr[i] representa el tiempo hasta el cual se enciende la i -ésima bombilla, comenzando desde el tiempo arr [yo – 1] . La tarea es encontrar la bombilla con el máximo tiempo de incandescencia. Si existe más de una bombilla con el mismo tiempo máximo de encendido, imprima lexicográficamente la mayor.
Ejemplos:
Entrada: S = “abcd”, arr[] = {9, 29, 49, 50}
Salida: c
Explicación:
‘c’ en el índice 0 tiene una duración = 9.
‘b’ en el índice 1 tiene una duración = arr[ 1] – arr[0] = 29 – 9 = 20
‘c’ en el índice 2 tiene una duración = arr[2] – arr[1]= 49 – 29 = 20
‘d’ en el índice 3 tiene una duración = arr[ 3] – arr[2]= 50 – 49 = 1
Dos bombillas, ‘b’ y ‘c’, tienen el máximo tiempo de encendido. Entre esos dos, ‘c’ es lexicográficamente más grande.Entrada: S = “spuda”, arr[] = {12, 23, 36, 46, 62}
Salida: a
Explicación:
‘s’ en el índice 0 tiene una duración = 12.
‘p’ en el índice 1 tiene una duración = arr[1] – arr[0] = 23-12 = 11.
‘u’ en el índice 2 tiene una duración = arr[2] – arr[1] = 36-23 = 13.
‘d’ en el índice 3 tiene una duración = arr[3] – arr[2] = 46-36 = 10.
‘a’ en el índice 4 tiene una duración = arr[4] – arr[3] = 62-46 = 16.
Por lo tanto, ‘a’ tiene tiempo máximo de brillo.
Enfoque: la idea es atravesar la array y, para cada elemento de la array, calcular arr[i] – arr[i – 1] . Luego, imprima la bombilla lexicográficamente más grande que tenga el máximo tiempo de incandescencia. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos maxDur y maxPos , para almacenar el tiempo de encendido y el índice de la bombilla con el tiempo máximo de encendido, respectivamente.
- Recorra la array dada y realice los siguientes pasos:
- Si la hora actual (arr[i] – arr[i – 1]) es menor que maxCurr , actualice maxCurr como maxCurr = arr[i] – arr[i – 1] .
- De lo contrario, si es igual a maxCurr , maxPos no contiene ningún índice válido y S[maxPos] es lexicográficamente más pequeño que S[i] , actualice maxPos como maxPos = i .
- Después de completar los pasos anteriores, imprima S[maxPos] como la salida requerida.
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 bulb
// having maximum glow
char longestLastingBulb(
vector<int> onTime, string s)
{
char ans;
int n = onTime.size();
// Initialize variables
int maxDur = INT_MIN;
int maxPos = INT_MIN;
int currentDiff = 0;
// Traverse the array consisting
// of glowing time of the bulbs
for (int i = 0; i < n; i++) {
// For 1st bulb
if (i == 0) {
currentDiff = onTime[i];
maxDur = currentDiff;
maxPos = i;
}
else {
// Calculate the glowing time
currentDiff = onTime[i]
- onTime[i - 1];
// Update the maximum glow
if (maxDur < currentDiff) {
maxDur = currentDiff;
maxPos = i;
}
// Find lexicographically
// largest bulb
else {
if (maxDur == currentDiff) {
char one = s[i];
char two = s[maxPos];
if (one > two) {
maxDur = currentDiff;
maxPos = i;
}
}
}
}
}
// Bulb with maximum time
ans = s[maxPos];
// Return the resultant bulb
return ans;
}
// Driver Code
int main()
{
string S = "spuda";
vector<int> arr = { 12, 23, 36, 46, 62 };
// Function call
cout << longestLastingBulb(arr, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the bulb
// having maximum glow
static char longestLastingBulb(
int []onTime, char []s)
{
char ans;
int n = onTime.length;
// Initialize variables
int maxDur = Integer.MIN_VALUE;
int maxPos = Integer.MIN_VALUE;
int currentDiff = 0;
// Traverse the array consisting
// of glowing time of the bulbs
for (int i = 0; i < n; i++) {
// For 1st bulb
if (i == 0) {
currentDiff = onTime[i];
maxDur = currentDiff;
maxPos = i;
}
else {
// Calculate the glowing time
currentDiff = onTime[i]
- onTime[i - 1];
// Update the maximum glow
if (maxDur < currentDiff) {
maxDur = currentDiff;
maxPos = i;
}
// Find lexicographically
// largest bulb
else {
if (maxDur == currentDiff) {
char one = s[i];
char two = s[maxPos];
if (one > two) {
maxDur = currentDiff;
maxPos = i;
}
}
}
}
}
// Bulb with maximum time
ans = s[maxPos];
// Return the resultant bulb
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "spuda";
int []arr = { 12, 23, 36, 46, 62 };
// Function call
System.out.print(longestLastingBulb(arr, S.toCharArray()));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach import sys INT_MIN = (sys.maxsize - 1) # Function to find the bulb # having maximum glow def longestLastingBulb(onTime, s): n = len(onTime) # Initialize variables maxDur = INT_MIN maxPos = INT_MIN currentDiff = 0 # Traverse the array consisting # of glowing time of the bulbs for i in range(n): # For 1st bulb if (i == 0): currentDiff = onTime[i] maxDur = currentDiff maxPos = i else: # Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1] # Update the maximum glow if (maxDur < currentDiff): maxDur = currentDiff maxPos = i # Find lexicographically # largest bulb else: if (maxDur == currentDiff): one = s[i] two = s[maxPos] if (one > two): maxDur = currentDiff maxPos = i # Bulb with maximum time ans = s[maxPos] # Return the resultant bulb return ans # Driver Code if __name__ == "__main__" : S = "spuda" arr = [ 12, 23, 36, 46, 62 ] # Function call print(longestLastingBulb(arr, S)) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the bulb
// having maximum glow
static char longestLastingBulb(
List<int> onTime, string s)
{
char ans;
int n = onTime.Count;
// Initialize variables
int maxDur = Int32.MinValue;
int maxPos = Int32.MinValue;
int currentDiff = 0;
// Traverse the array consisting
// of glowing time of the bulbs
for (int i = 0; i < n; i++) {
// For 1st bulb
if (i == 0) {
currentDiff = onTime[i];
maxDur = currentDiff;
maxPos = i;
}
else {
// Calculate the glowing time
currentDiff = onTime[i]
- onTime[i - 1];
// Update the maximum glow
if (maxDur < currentDiff) {
maxDur = currentDiff;
maxPos = i;
}
// Find lexicographically
// largest bulb
else {
if (maxDur == currentDiff) {
char one = s[i];
char two = s[maxPos];
if (one > two) {
maxDur = currentDiff;
maxPos = i;
}
}
}
}
}
// Bulb with maximum time
ans = s[maxPos];
// Return the resultant bulb
return ans;
}
static void Main() {
string S = "spuda";
List<int> arr = new List<int>(new int[] {12, 23, 36, 46, 62});
// Function call
Console.Write(longestLastingBulb(arr, S));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function to find the bulb
// having maximum glow
function longestLastingBulb(onTime, s)
{
let ans;
let n = onTime.length;
// Initialize variables
let maxDur = Number.MIN_VALUE;
let maxPos = Number.MIN_VALUE;
let currentDiff = 0;
// Traverse the array consisting
// of glowing time of the bulbs
for(let i = 0; i < n; i++)
{
// For 1st bulb
if (i == 0)
{
currentDiff = onTime[i];
maxDur = currentDiff;
maxPos = i;
}
else
{
// Calculate the glowing time
currentDiff = onTime[i] -
onTime[i - 1];
// Update the maximum glow
if (maxDur < currentDiff)
{
maxDur = currentDiff;
maxPos = i;
}
// Find lexicographically
// largest bulb
else
{
if (maxDur == currentDiff)
{
let one = s[i];
let two = s[maxPos];
if (one > two)
{
maxDur = currentDiff;
maxPos = i;
}
}
}
}
}
// Bulb with maximum time
ans = s[maxPos];
// Return the resultant bulb
return ans;
}
// Driver code
let S = "spuda";
let arr = [ 12, 23, 36, 46, 62 ];
// Function call
document.write(longestLastingBulb(arr, S));
// This code is contributed by divyesh072019
</script>
a
Complejidad temporal: O(N)
Espacio auxiliar: O(1)