Solution: First, if $f(x)=g(x) h(x), g, h \in Z[x]$, then $n \leqslant 7$.
Assume without loss of generality that $\partial(g(x)) \leqslant \partial(h(x))$, then $\partial(g(x)) \leqslant\left[\frac{n}{2}\right]$.
Let $\left|f\left(x_{i}\right)\right|=1,1 \leqslant i \leqslant m, m \geqslant\left[\frac{n}{2}\right]+1$, since $f\left(x_{i}\right)= \pm 1$, it follows that $g\left(x_{i}\right)= \pm 1$. Assume without loss of generality that among $x_{1}, x_{2}, \cdots, x_{m}$, the number of $x_{i}$ for which $g\left(x_{i}\right)=1$ is no less than the number of $x_{i}$ for which $g\left(x_{i}\right)=-1$. Let these be $x_{1}<x_{2}<\cdots<x_{l}, l \geqslant \frac{m}{2}$, then
$$
g(x)-1=\left(x-x_{1}\right)\left(x-x_{2}\right) \cdots\left(x-x_{1}\right) \cdot p(x), p(x) \in Z[x],
$$

Since $\partial(g(x)) \leqslant\left[\frac{n}{2}\right]<\left[\frac{n}{2}\right]+1 \leqslant m, l \leqslant \partial(g(x))$, it follows that $1<m$. Also, $g\left(x_{l+1}\right)=-1$, so $\left(x_{i+1}-x_{1}\right)\left(x_{i+1}-x_{2}\right) \cdots\left(x_{i+1}-x_{1}\right) p\left(x_{i+1}\right)=-2$.
This implies $l \leqslant 3$.
When $l=3$, there is at most one integer $a$ such that $\left(a-x_{1}\right)\left(a-x_{2}\right)\left(a-x_{3}\right)=-2$, which gives $m \leqslant 4$.
When $l \leqslant 2$, by $l \geqslant \frac{m}{2}$, we also have $m \leqslant 4$. Since $m \geqslant\left[\frac{n}{2}\right]+1$, it follows that $n \leqslant 7$, hence $k \leqslant 7$.
When $n=7$, take $f(x)=[1+x(x-3)(x-1)][1+x(x-3)(x-2)(x-1)]$. Then for $x=0,1,2,3$, we have $|f(x)|=1$, so $k=7$.
Consider the following problem: Find the smallest $k \in \mathbf{N}^{\boldsymbol{*}}$, such that for any integer-coefficient polynomial $f(x)$ (with leading coefficient 1) of degree $n > k$, if there are at least $\left[\frac{n}{2}\right]+1$ distinct integers $x$ for which $|f(x)|=1$, then $f(x)$ cannot be factored into the product of two non-constant integer-coefficient polynomials.