app定制开发最牛青岗科技公司_做网站能挣多少钱_郑州seo顾问热狗hotdoger_seo网络排名优化方法

1、题目链接

11. 盛最多水的容器

2、题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

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

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

3、核心思路

1、暴力破解

• 两层for循环遍历，记录所有的面积，留下最大的面积

2、双指针

思路：
使用双指针从数组的两端开始向中间移动。每次移动较矮的指针，计算当前面积并更新最大值。这样可以确保在移动过程中不会错过可能的更大面积。

步骤：

1. 初始化左指针 left = 0 和右指针 right = len(height) - 1，以及最大面积 max_area = 0。
2. 当 left < right 时循环：
   • 计算当前容器的面积：current_area = (right - left) * min(height[left], height[right])。
   • 更新 max_area。
   • 移动较矮的指针（若左指针较矮则右移，否则左移）。
3. 返回 max_area。

正确性证明：
每次移动较矮的指针，可以确保不会错过更大的面积。因为容器的容量受限于较矮的一边，移动较高的指针无法增加容量，而移动较矮的指针可能找到更高的边界。

---

代码实现

Java

class Solution {public int maxArea(int[] height) {int maxArea = 0;int left = 0;int right = height.length - 1;while (left < right) {int currentHeight = Math.min(height[left], height[right]);int currentArea = currentHeight * (right - left);maxArea = Math.max(maxArea, currentArea);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;}
}

C++

class Solution {
public:int maxArea(vector<int>& height) {int max_area = 0;int left = 0, right = height.size() - 1;while (left < right) {int current_height = min(height[left], height[right]);max_area = max(max_area, current_height * (right - left));if (height[left] < height[right]) {left++;} else {right--;}}return max_area;}
};

Go

func maxArea(height []int) int {maxArea := 0left, right := 0, len(height)-1for left < right {currentHeight := min(height[left], height[right])currentArea := currentHeight * (right - left)if currentArea > maxArea {maxArea = currentArea}if height[left] < height[right] {left++} else {right--}}return maxArea
}func min(a, b int) int {if a < b {return a}return b
}

Python

class Solution:def maxArea(self, height: List[int]) -> int:max_area = 0left, right = 0, len(height) - 1while left < right:current_height = min(height[left], height[right])current_area = current_height * (right - left)max_area = max(max_area, current_area)if height[left] < height[right]:left += 1else:right -= 1return max_area

JavaScript

var maxArea = function(height) {let maxArea = 0;let left = 0, right = height.length - 1;while (left < right) {const currentHeight = Math.min(height[left], height[right]);const currentArea = currentHeight * (right - left);maxArea = Math.max(maxArea, currentArea);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
};

---

复杂度分析：

• 时间复杂度：O(n)，仅需一次遍历数组。
• 空间复杂度：O(1)，仅使用常数空间。