LeetCode 665: Matriz não decrescente

Question

Estou postando uma solução para a "Matriz não decrescente" do LeetCode. Se você gostaria de revisar, por favor, faça. Obrigado!

Problema

Dado um array numscom ninteiros, sua tarefa é verificar se ele pode se tornar não decrescente modificando no máximo 1 elemento.

Definimos que um array é não decrescente se for nums[i] <= nums[i + 1]válido para cada i (baseado em 0) tal que ( 0 <= i <= n - 2).

Exemplo 1:

• Entrada: nums = [4,2,3]
• Resultado: verdadeiro
• Explicação: Você pode modificar os primeiros 4 para 1 para obter uma matriz não decrescente.

Exemplo 2:

• Entrada: nums = [4,2,1]
• Resultado: falso
• Explicação: Você não pode obter uma matriz não decrescente modificando no máximo um elemento.

Restrições:

• 1 <= n <= 10 ^ 4
• -10 ^ 5 <= nums[i] <= 10 ^ 5

Código

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

struct Solution {
    using ValueType = std::int_fast32_t;
    static const bool checkPossibility(
        std::vector<int>& nums
    ) {

        if (std::size(nums) < 3) {
            return true;
        }

        ValueType max_changes = 0;

        for (ValueType index = 1; max_changes < 2 && index < std::size(nums); ++index) {
            if (nums[index - 1] > nums[index]) {
                ++max_changes;

                if (index - 2 < 0 || nums[index - 2] <= nums[index]) {
                    nums[index - 1] = nums[index];

                } else {
                    nums[index] = nums[index - 1];
                }
            }
        }

        return max_changes < 2;
    }
};


int main() {
    std::vector<int> nums = {3, 4, 2, 3};
    std::cout << std::to_string(Solution().checkPossibility(nums) == false) << "\n";
    return 0;
}

Answer 1

Evite o manuseio desnecessário de casos especiais

Você sai mais cedo se o tamanho do array for menor que 3, mas isso é desnecessário: o resto do código já lida com arrays de tamanho 0, 1 e 2 corretamente. Você pode salvar um ciclo se alimentá-lo com uma pequena matriz, mas paga por esse cheque com um ou dois ciclos para cada vez que a função é chamada com std::size(nums)> 2.

Use std::size_tpara índices

Você fez indexum std::int_fast32_t, mas ele tem um tamanho diferente (provável) e uma sinalização diferente do resultado de std::size(nums). Isso significa que o compilador deveria ter avisado sobre uma comparação entre inteiros assinados e não assinados. Embora as coisas funcionem aqui, já que você sabe que o tamanho da matriz de entrada é restrito, é melhor usar std::size_taqui para evitar o aviso do compilador. O desempenho provavelmente não será diferente, pois indexpode ser mantido em um registro da CPU o tempo todo.

Não há necessidade de usar std::to_string()ao usar <<em umstd::ostream

Ao gravar em a std::ostream, operator<<já fará com que o argumento seja formatado, portanto, não há necessidade de chamar std::to_string(). Na verdade, você pode dizer ao stream para formatar um boolcomo texto:

int main() {
    std::vector<int> nums = {3, 4, 2, 3};
    std::cout << std::boolalpha << Solution().checkPossibility(nums) << "\n";
}