The best solution is to get your site into the HSTS preload list. You can do that here: https://hstspreload.org/ - this adds the site to the Chrome list, and most other major browsers (Firefox, Opera, Safari, IE 11 and Edge) have an HSTS preload list based on the Chrome list. Once that happens and the browser updates, users will always use https, even if they ask for http.
A 301 redirect will offer some lasting protection as it can be cached but it's not really that great. The goal here is to take the first step to get on HTTPS and then longer term the sites can consider HSTS and eventually preloading.