|
| 1 | +```text |
| 2 | +题目: 给你n个非负整数a1,a2,...,an,每个数代表坐标中的一个点(i, ai) |
| 3 | + 在坐标内画n条垂直线,垂直线i的两个端点分别为(i, ai)和 (i,0) |
| 4 | + 找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水 |
| 5 | + 说明: 你不能倾斜容器,且 n 的值至少为 2 |
| 6 | + 示例: |
| 7 | + 输入: [1,8,6,2,5,4,8,3,7] |
| 8 | + 输出: 49 |
| 9 | +1.双重暴力循环: |
| 10 | + [1]思路: 像选择排序一样遍历,每遍历到一个求盛水量,并保存最大的盛水量 |
| 11 | + [2]实现: |
| 12 | + class Solution { |
| 13 | + public int maxArea(int[] height) { |
| 14 | + int maxArea = 0; |
| 15 | + for (int i = 0; i < height.length-1; i++) { |
| 16 | + for (int j = i+1; j < height.length; j++) { |
| 17 | + // 盛水量= Math.min(两个边界)*两个边界的距离 |
| 18 | + maxArea = Math.max(maxArea, (j - i) * Math.min(height[i], height[j])); |
| 19 | + } |
| 20 | + } |
| 21 | + return maxArea; |
| 22 | + } |
| 23 | + } |
| 24 | + [3]复杂度分析: |
| 25 | + (1)时间复杂度: O(N^2),N为数组元素个数 |
| 26 | + (2)空间复杂度: O(1) |
| 27 | +2.双指针: |
| 28 | + [1]思路: |
| 29 | + (1)盛水量的决定因素有两个: 两边界的最短值,两边界的距离; |
| 30 | + (2)使用双指针分别指向数组的首尾位置求盛水量; |
| 31 | + (3)再将两边界中较短的位置向中间缩进一位再求盛水量,取最大盛水量保存; |
| 32 | + (较短的边界决定盛水高度,移动较短边界的位置才有可能得到更大的盛水量) |
| 33 | + (每次移动位置两边界的距离都缩小1,因此只有较短边界的位置移动后,盛水高度变高的更快时,才能得到更大盛水量) |
| 34 | + (4)不断重复(3),直到右指针不大于左指针; |
| 35 | + [2]实现: |
| 36 | + class Solution { |
| 37 | + public int maxArea(int[] height) { |
| 38 | + // 定义两个指针 |
| 39 | + int left = 0, right = height.length - 1; |
| 40 | + // 定义最大盛水量 |
| 41 | + int maxArea = (right - left) * Math.min(height[left], height[right]); |
| 42 | + // 按要求进行双指针的移动遍历 |
| 43 | + while (left < right) { |
| 44 | + if(height[left]<height[right]){ |
| 45 | + left++; |
| 46 | + }else { |
| 47 | + right--; |
| 48 | + } |
| 49 | + maxArea = Math.max(maxArea,(right - left) * Math.min(height[left], height[right])); |
| 50 | + } |
| 51 | + return maxArea; |
| 52 | + } |
| 53 | + } |
| 54 | + [3]复杂度分析: |
| 55 | + (1)时间复杂度: O(N),N为数组元素个数 |
| 56 | + (2)空间复杂度: O(1) |
| 57 | +``` |
0 commit comments