leetcode 11盛水最多的容器（双指针法）

￡神魔★判官ぃ 2023-06-11 05:23 96阅读 0赞

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

说明：你不能倾斜容器，且 n 的值至少为 2。
在这里插入图片描述

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：刚开始想暴力遍历，取2点之间的最低点再算面积，再更新最大值。
但是这里双指针能做。

  1. class Solution {
  3.     public int maxArea(int[] height) {
  6.         int res = 0;
  7.         int i = 0;
  8.         int j = height.length-1;
  10.         while(i<j)
  11.         {
  13.           res  =  height[i]>height[j]?Math.max(res,height[j--]*(j-i+1)):
  14.             Math.max(res,height[i++]*(j-i+1));
  16.         }
  18.         return res;
  19.     }
  20. }

发表评论

表情：
评论列表 （有 0 条评论，96人围观）

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

相关阅读