11 盛水最多的容器

ゞ 浴缸里的玫瑰 2024-02-19 15:41 137阅读 0赞

每每看及官方解法,总羞愧难当,官方解法简洁易懂,何时才能达到这种水平呢?只有不断努力了。

  1. package leetCode;
  2. //官方解法
  3. class Solution {
  4. public int maxArea(int[] height) {
  5. int maxarea = 0, l = 0, r = height.length - 1;
  6. while (l < r) {
  7. maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
  8. if (height[l] < height[r])
  9. l++;
  10. else
  11. r--;
  12. }
  13. return maxarea;
  14. }
  15. }
  16. //我的解法,解法不正确
  17. //我的思路:每次比较单侧,利用偏移量来比较,和官方解法对比后,感觉我的思路和暴力法更相似
  18. public class BestWaterContainer {
  19. public static void main(String[] args) {
  20. //int[] heights= {10,9,8,7,6,5,4,3,2,1};//25
  21. //int[] heights= {1,8,6,2,5,4,8,3,7};//49
  22. //int[] heights= {1,1};
  23. //int[] heights= {1,2,1};
  24. int[] heights= {2,3,10,5,7,8,9};//36
  25. System.out.println(maxArea(heights));
  26. }
  27. public static int maxArea(int[] heights) {
  28. //初始化最大值
  29. int max = getAcreage(0, heights.length-1, heights);
  30. System.out.println("初始化的Max:"+ max);
  31. int i = 0;
  32. int j = heights.length - 1;
  33. int offsetLeft = 1;
  34. int offsetRight = 1;
  35. while ((i+offsetLeft)<=(j+offsetRight)&&(i+offsetLeft)<heights.length||(j-offsetRight)>= 0) {
  36. // 首先是0和lenght-1,然后让其分别与单侧相邻点比较,取大者,计算值,若值更大者留下
  37. if ((i+offsetLeft)<heights.length&&heights[i]< heights[i + offsetLeft]) {
  38. int area = getAcreage(i + offsetLeft, j, heights);
  39. if (area > max) {
  40. max = area;
  41. i = i + offsetLeft;
  42. }
  43. //System.out.println("循环中的max:i :"+max);
  44. }
  45. if ((j-offsetRight)>= 0&&heights[j] < heights[j - offsetRight]) {
  46. int area = getAcreage(i, j-offsetRight, heights);
  47. if (area > max) {
  48. max = area;
  49. j = j - offsetRight;
  50. }
  51. //System.out.println("循环中的max:j :"+max);
  52. }
  53. offsetLeft++;
  54. offsetRight++;
  55. }
  56. return max;
  57. }
  58. public static int getAcreage(int startPoint, int endPoint, int heights[]) {
  59. int height = Math.min(heights[startPoint], heights[endPoint]);
  60. int wide = endPoint - startPoint;
  61. return wide * height;
  62. }
  63. }

发表评论

表情:
评论列表 (有 0 条评论,137人围观)

还没有评论,来说两句吧...

相关阅读

    相关 11. 容器

    [题目][Link 1] 给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为