Trivially, best possible is $$\begin{pmatrix}
1&1&\dots&&1&2\\
\vdots&&&&2&3\\
\vdots&&&& \vdots & \vdots \\
1&1&\dots &&n-1 &n\\
1&1&\dots &n-1 &n&n\\
\vdots&&&& \vdots & \vdots \\
n&n&\dots&&n  & n \\
\end{pmatrix}$$ with constant antidiagonals, which has $(n-1)(n^2-1)=O(n^3)$  turning points. Or am I missing something?  
(BTW is there a Latex command for rising `\ddots`?)