LeetCode 665: неубывающий массив

Question

Я отправляю решение для LeetCode «Неубывающий массив». Если вы хотите просмотреть, сделайте это. Спасибо!

Проблема

Учитывая массив numsс nцелыми числами, ваша задача - проверить, может ли он стать неубывающим, изменив не более 1 элемента.

Мы определяем, что массив не убывает, если nums[i] <= nums[i + 1]выполняется для каждого i (на основе 0), такого что ( 0 <= i <= n - 2).

Пример 1:

• Ввод: nums = [4,2,3]
• Выход: правда
• Объяснение: Вы можете изменить первые 4 на 1, чтобы получить неубывающий массив.

Пример 2:

• Ввод: nums = [4,2,1]
• Выход: ложь
• Объяснение: Вы не можете получить неубывающий массив, изменив не более одного элемента.

Ограничения:

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

Код

// 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

Избегайте ненужной обработки особых случаев

Вы выходите раньше, если размер массива меньше 3, но в этом нет необходимости: остальная часть кода уже правильно обрабатывает массивы размера 0, 1 и 2. Вы можете сохранить цикл, если скармливаете ему небольшой массив, но вы платите за эту проверку одним или двумя циклами за каждый раз, когда функция вызывается с std::size(nums)> 2.

Использовать std::size_tдля индексов

Вы сделали , но имеет другой размер (вероятно) и другую знаковость , чем результат . Это означает, что компилятор должен был предупредить вас о сравнении целых чисел со знаком и без знака. Хотя здесь все работает, поскольку вы знаете, что размер входного массива ограничен, лучше всего использовать здесь, чтобы избежать предупреждения компилятора. Производительность, скорее всего, не будет отличаться ни на один бит, поскольку может всегда храниться в регистре ЦП.indexstd::int_fast32_tstd::size(nums)std::size_tindex

Нет необходимости использовать std::to_string()при использовании <<наstd::ostream

При записи в a std::ostream, operator<<аргумент уже будет отформатирован, поэтому вызывать его не нужно std::to_string(). Фактически, вы можете указать потоку форматировать boolкак текст:

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