  We present efficient data structures for submatrix maximum queries in Monge
matrices and Monge partial matrices. For $n\times n$ Monge matrices, we give a
data structure that requires O(n) space and answers submatrix maximum queries
in $O(\log n)$ time. The best previous data structure [Kaplan et al., SODA`12]
required $O(n \log n)$ space and $O(\log^2 n)$ query time. We also give an
alternative data structure with constant query-time and $ O(n^{1+\varepsilon})$
construction time and space for any fixed $\varepsilon<1$. For $n\times n$ {\em
partial} Monge matrices we obtain a data structure with O(n) space and $O(\log
n \cdot \alpha(n))$ query time. The data structure of Kaplan et al. required
$O(n \log n \cdot \alpha(n))$ space and $O(\log^2 n)$ query time.
  Our improvements are enabled by a technique for exploiting the structure of
the upper envelope of Monge matrices to efficiently report column maxima in
skewed rectangular Monge matrices. We hope this technique can be useful in
obtaining faster search algorithms in Monge partial matrices. In addition, we
give a linear upper bound on the number of breakpoints in the upper envelope of
a Monge partial matrix. This shows that the inverse Ackermann $\alpha(n)$ term
in the analysis of the data structure of Kaplan et. al is superfluous.
