2389. Subsequência Mais Longa com Soma Limitada

Para resolver este problema, podemos ordenar o array em ordem crescente e, para cada consulta, encontrar o maior comprimento de subsequência cuja soma não exceda o valor da consutla. Uma abordagem eficiente utiliza soma prefixada e busca binária.

Complexidade de Tempo: A ordenação é O(n log n) e cada consulta é O(log n), resultando em O((n + m) log n).

Complexidade de Espaço: O(m + log n) para armazenar respostas e a pilha de recursão da ordenação.

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> responderConsultas(vector<int>& numeros, vector<int>& consultas) {
        sort(numeros.begin(), numeros.end());
        for (int i = 1; i < numeros.size(); i++) {
            numeros[i] += numeros[i - 1];
        }
        vector<int> respostas;
        for (int q : consultas) {
            auto it = upper_bound(numeros.begin(), numeros.end(), q);
            respostas.push_back(it - numeros.begin());
        }
        return respostas;
    }
};

2390. Remover Estrelas de uma String

Este problema pode ser resolvido simulando uma pilha. Ao iterar sobre os caracteres, se encontrar uma estrela ('*'), remova o último caractere adicionado; caso contrário, adicione o caractere à pilha.

Complexidade de Tempo: O(n), onde n é o comprimento da string.

Complexidade de Espaço: O(n) para armazenar os caracteres na pilha.

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string removerEstrelas(string texto) {
        vector<char> pilha;
        for (char c : texto) {
            if (c == '*') {
                if (!pilha.empty()) pilha.pop_back();
            } else {
                pilha.push_back(c);
            }
        }
        string resultado(pilha.begin(), pilha.end());
        return resultado;
    }
};

2391. Tempo Mínimo Total para Coletar Lixo

A solução envolve simular o processo de coleta. Para cada casa, some o número de lixos ao tempo total e registre a posição mais distante para cada tipo de lixo (metal, papel, vidro). Em seguida, some as distâncias percorridas pelos caminhões até essas posições.

Complexidade de Tempo: O(nL), onde n é o número de casas e L é o comprimento médio das strings de lixo.

Complexidade de Espaço: O(1) adicional, exceto para armazenar o resultado.

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int tempoMinimoColeta(vector<string>& lixos, vector<int>& viagens) {
        int totalCasas = lixos.size();
        int tempoTotal = 0;
        int posMetal = 0, posPapel = 0, posVidro = 0;
        
        for (int i = 0; i < totalCasas; i++) {
            tempoTotal += lixos[i].size();
            for (char tipo : lixos[i]) {
                if (tipo == 'M') posMetal = i;
                else if (tipo == 'P') posPapel = i;
                else posVidro = i;
            }
        }
        
        vector<int> distanciasAcumuladas(totalCasas - 1);
        if (totalCasas > 1) distanciasAcumuladas[0] = viagens[0];
        for (int i = 1; i < totalCasas - 1; i++) {
            distanciasAcumuladas[i] = distanciasAcumuladas[i - 1] + viagens[i];
        }
        
        if (posMetal > 0) tempoTotal += distanciasAcumuladas[posMetal - 1];
        if (posPapel > 0) tempoTotal += distanciasAcumuladas[posPapel - 1];
        if (posVidro > 0) tempoTotal += distanciasAcumuladas[posVidro - 1];
        
        return tempoTotal;
    }
};

2392. Construir Matriz sob Condições Dadas

O problema é resolvido usando ordenação topológica para determinar a ordem dos números nas linhas e colunas. Primeiro, realize a ordenação topológica separadamente para as condições de linhas e colunas. Se não houver ordenação válida, retorne uma matriz vazia. Em seguida, preencha a matriz com base nas classificações obtidas.

Complexidade de Tempo: O(k + m) para as duas ordenações topológicas, onde m é o número de condições. O preenchimento da matriz é O(k).

Complexidade de Espaço: O(k²) para armazenar a estrutura de dados da ordenação e a resposta.

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> ordenacaoTopologica(int numVertices, vector<vector<int>>& restricoes) {
        vector<vector<int>> adjacentes(numVertices + 1);
        vector<int> grauEntrada(numVertices + 1, 0);
        
        for (auto& cond : restricoes) {
            int origem = cond[0];
            int destino = cond[1];
            adjacentes[origem].push_back(destino);
            grauEntrada[destino]++;
        }
        
        queue<int> fila;
        for (int vertice = 1; vertice <= numVertices; vertice++) {
            if (grauEntrada[vertice] == 0) {
                fila.push(vertice);
            }
        }
        
        vector<int> ordenacao;
        while (!fila.empty()) {
            int atual = fila.front();
            fila.pop();
            ordenacao.push_back(atual);
            
            for (int vizinho : adjacentes[atual]) {
                grauEntrada[vizinho]--;
                if (grauEntrada[vizinho] == 0) {
                    fila.push(vizinho);
                }
            }
        }
        
        if (ordenacao.size() != numVertices) return {};
        return ordenacao;
    }
    
    int indiceDe(vector<int>& ordenacao, int valor) {
        for (int i = 0; i < ordenacao.size(); i++) {
            if (ordenacao[i] == valor) return i;
        }
        return -1;
    }
    
    vector<vector<int>> montarMatriz(int k, vector<vector<int>>& condLinhas, vector<vector<int>>& condColunas) {
        auto ordemLinhas = ordenacaoTopologica(k, condLinhas);
        auto ordemColunas = ordenacaoTopologica(k, condColunas);
        
        if (ordemLinhas.empty() || ordemColunas.empty()) return {};
        
        vector<vector<int>> matriz(k, vector<int>(k, 0));
        for (int num = 1; num <= k; num++) {
            int linha = indiceDe(ordemLinhas, num);
            int coluna = indiceDe(ordemColunas, num);
            matriz[linha][coluna] = num;
        }
        
        return matriz;
    }
};