Based on a simple projection of the solution increments of the underlying partial differential equations (PDEs) at each local time level, this paper presents a difference scheme for nonlinear Hamilton-Jacobi (H-J) equations with varying time and space grids. The scheme is of good consistency and monotone under a local CFL-type condition. Moreover, one may deduce a conservative local time step scheme similar to Osher and Sanders scheme approximating hyperbolic conservation law (CL) from our scheme according to the close relation between CLs and H-J equations. Second order accurate schemes are constructed by combining the reconstruction technique with a second order accurate Runge-Kutta time discretization scheme or a Lax-Wendroff type method. They keep some good properties of the global time step schemes, including stability and convergence, and can be applied to solve numerically the initial-boundary-value problems of viscous H-J equations. They are also suitable to parallel computing. Numerical errors and the experimental rate of convergence in the Lp-norm, p=1, 2, and ∞, are obtained for several one-and two-dimensional problems. The results show that the present schemes are of higher order accuracy.