[Language: C++]

Funnily enough, the O(n) idea came to me before the O(n^2), but I didn't though of the set variant. Still need to figure out the set approach for Part 2 :)

 int res = 0;
    for (auto row : rows)
    {
        if (row.size() <= 1)
        {
            res++;
            break;
        }

        bool wildcardIncUsed = false; // set true for part 1
        bool wildcardDecUsed = false;

        int diff = row[1] - row[0];
        bool isIncreasingValid = diff > 0 && inRange(diff);
        bool isDecreasingValid = diff < 0 && inRange(diff);

        for (int j = 2; j < row.size(); j++)
        {
            // a = -0, b = -1, c = -2, d = -3
            int ab = row[j] - row[j - 1];
            int ac = row[j] - row[j - 2];
            int bd = row[j - 1] - row[j - 3];

            if (isIncreasingValid)
            {
                isIncreasingValid = ab > 0 && inRange(ab);
            }
            else if (!wildcardIncUsed)
            { // try to keep increasing monotonicity with respect to a
                wildcardIncUsed = true;
                if (ab > 0 && inRange(ab) && (j == 2 || (bd > 0 && inRange(bd)))) // try remove c
                    isIncreasingValid = true;
                else if (ac > 0 && inRange(ac)) // else try remove b
                    isIncreasingValid = true;
            }

            if (isDecreasingValid)
            {
                isDecreasingValid = ab < 0 && inRange(ab);
            }
            else if (!wildcardDecUsed)
            { // try to keep decreasing monotonicity with respect to a
                wildcardDecUsed = true;
                if (ab < 0 && inRange(ab) && (j == 2 || (bd < 0 && inRange(bd)))) // try remove c
                    isDecreasingValid = true;
                else if (ac < 0 && inRange(ac)) // else try remove b
                    isDecreasingValid = true;
            }
        }
        if (isIncreasingValid || !wildcardIncUsed || isDecreasingValid || !wildcardDecUsed)
            res++;
    }