Jenna Rajchgot observed that the Castelnuovo-Mumford regularity of matrix Schubert varieties is computed by the degrees of the corresponding Grothendieck polynomials. We give a formula for these degrees. Indeed, we compute the leading terms of the top degree pieces of Grothendieck polynomials and give a complete description of when two Grothendieck polynomials have the same top degree piece (up to scalars). Our formulas rely on some new facts about major index of permutations.