个人随笔
目录
leetcode11. 盛最多水的容器:双指针法
2021-09-06 12:29:27

问题描述

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器。

解题2方法

  1. /**
  2. * 11. 盛最多水的容器
  3. * https://leetcode-cn.com/problems/container-with-most-water/
  4. * @author 爱吃鱼的乌贼
  5. *
  6. */
  7. public class Leetcode11 {
  8. /**
  9. * 用双指针的方法,让两个指针分别指向第一个和最后一个值,因为能够剩多少水,靠的是较小的挡板,所以
  10. * 哪一个指针对应的小,就移动哪一个,毕竟移动较大的指针是没有意义的,因为两个指针的距离是变小的,容量又是
  11. * 小的挡板*距离,所以移动高的挡板,没有意义,不可能大于不移动的容量
  12. * @param height
  13. * @return
  14. */
  15. public int maxArea(int[] height) {
  16. int len = height.length;
  17. //开始下标
  18. int first = 0;
  19. //结束下标
  20. int last = len-1;
  21. //最大容量
  22. int max = 0;
  23. //如果开始下标小于结束下标,则进行移动判定
  24. while(first<last) {
  25. //1、获取下标之间的距离
  26. int t = last-first;
  27. //2、获取叫矮的挡板值
  28. int first_value = height[first];
  29. int last_value = height[last];
  30. int min = getMin(first_value, last_value);
  31. //3、获取当前的容量
  32. int h = t*min;
  33. if(h>max) {
  34. max=h;
  35. }
  36. //4、移动较小的下标
  37. if(first_value<last_value) {
  38. first++;
  39. }else {
  40. last--;
  41. }
  42. }
  43. return max;
  44. }
  45. public int getMin(int first,int second) {
  46. if(first>=second) {
  47. return second;
  48. }else {
  49. return first;
  50. }
  51. }
  52. public static void main(String[] args) {
  53. int[] height = new int[] {1,8,6,2,5,4,8,3,7};
  54. System.out.println(new Leetcode11().maxArea(height));
  55. }
  56. }

总结

我一开始还以为用动态规划法,后面发现没有用,最后的选择还是需要把前面的都算一遍,所以怎么想都想不到解决办法,最后看了题解才发现有一种解法叫做:双指针法。

果然如果不看题解,靠自己想,怎么都想不到的,只有看了题解才会知道!

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 57

啊!这个可能是世界上最丑的留言输入框功能~


当然,也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号