题目: 盛最多水的容器

来自智得网
跳转至： 导航、​ 搜索

方法一：暴力法

暴力法是最直接的解决方法，它的思路是遍历所有可能的容器组合，计算它们的面积，并找到最大的面积。 具体步骤：

  1. 初始化最大面积为0。
  2. 使用两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。
  3. 计算当前容器的面积，即两个指针之间的距离乘以较小的高度。
  4. 更新最大面积为当前面积和最大面积中的较大值。
  5. 将较小的指针向内移动一步，重复步骤3和步骤4，直到两个指针相遇。
#include <iostream>
#include <vector>

using namespace std;

int maxArea(vector<int>& height) {
    int n = height.size();
    int maxArea = 0;

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int area = min(height[i], height[j]) * (j - i);
            maxArea = max(maxArea, area);
        }
    }

    return maxArea;
}

int main() {
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int result = maxArea(height);
    cout << "Max area: " << result << endl;

    return 0;
}

import java.util.Arrays;

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int maxArea = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int area = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, area);
            }
        }

        return maxArea;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        Solution solution = new Solution();
        int result = solution.maxArea(height);
        System.out.println("Max area: " + result);
    }
}

package main

import "fmt"

func maxArea(height []int) int {
    n := len(height)
    maxArea := 0

    for i := 0; i < n-1; i++ {
        for j := i + 1; j < n; j++ {
            area := min(height[i], height[j]) * (j - i)
            maxArea = max(maxArea, area)
        }
    }

    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    height := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
    result := maxArea(height)
    fmt.Println("Max area:", result)
}

def maxArea(height):
    n = len(height)
    maxArea = 0

    for i in range(n - 1):
        for j in range(i + 1, n):
            area = min(height[i], height[j]) * (j - i)
            maxArea = max(maxArea, area)

    return maxArea

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
result = maxArea(height)
print("Max area:", result)

function maxArea(height) {
    let n = height.length;
    let maxArea = 0;

    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            let area = Math.min(height[i], height[j]) * (j - i);
            maxArea = Math.max(maxArea, area);
        }
    }

    return maxArea;
}

let height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
let result = maxArea(height);
console.log("Max area:", result);

方法二：双指针法

双指针法是一种优化的方法，它通过不断移动较小的指针来缩小搜索范围。 具体步骤：

  1. 初始化最大面积为0。
  2. 使用两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。
  3. 计算当前容器的面积，即两个指针之间的距离乘以较小的高度。
  4. 更新最大面积为当前面积和最大面积中的较大值。
  5. 将较小的指针向内移动一步，重复步骤3和步骤4，直到两个指针相遇。
#include <iostream>
#include <vector>

using namespace std;

int maxArea(vector<int>& height) {
    int n = height.size();
    int maxArea = 0;
    int left = 0, right = n - 1;

    while (left < right) {
        int area = min(height[left], height[right]) * (right - left);
        maxArea = max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

int main() {
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int result = maxArea(height);
    cout << "Max area: " << result << endl;

    return 0;
}

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int maxArea = 0;
        int left = 0, right = n - 1;

        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        Solution solution = new Solution();
        int result = solution.maxArea(height);
        System.out.println("Max area: " + result);
    }
}

package main

import "fmt"

func maxArea(height []int) int {
    n := len(height)
    maxArea := 0
    left, right := 0, n-1

    for left < right {
        area := min(height[left], height[right]) * (right - left)
        maxArea = max(maxArea, area)

        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    height := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
    result := maxArea(height)
    fmt.Println("Max area:", result)
}

def maxArea(height):
    n = len(height)
    maxArea = 0
    left, right = 0, n - 1

    while left < right:
        area = min(height[left], height[right]) * (right - left)
        maxArea = max(maxArea, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return maxArea

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
result = maxArea(height)
print("Max area:", result)

function maxArea(height) {
    let n = height.length;
    let maxArea = 0;
    let left = 0, right = n - 1;

    while (left < right) {
        let area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

let height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
let result = maxArea(height);
console.log("Max area:", result);

方法三：动态规划法

动态规划法通过存储子问题的解来避免重复计算，从而提高效率。 具体步骤：

  1. 初始化最大面积为0。
  2. 使用两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。
  3. 计算当前容器的面积，即两个指针之间的距离乘以较小的高度。
  4. 更新最大面积为当前面积和最大面积中的较大值。
  5. 将较小的指针向内移动一步，重复步骤3和步骤4，直到两个指针相遇。
#include <iostream>
#include <vector>

using namespace std;

int maxArea(vector<int>& height) {
    int n = height.size();
    int maxArea = 0;
    int left = 0, right = n - 1;

    while (left < right) {
        int h = min(height[left], height[right]);
        int area = h * (right - left);
        maxArea = max(maxArea, area);

        while (left < right && height[left] <= h) {
            left++;
        }
        while (left < right && height[right] <= h) {
            right--;
        }
    }

    return maxArea;
}

int main() {
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int result = maxArea(height);
    cout << "Max area: " << result << endl;

    return 0;
}

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int maxArea = 0;
        int left = 0, right = n - 1;

        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int area = h * (right - left);
            maxArea = Math.max(maxArea, area);

            while (left < right && height[left] <= h) {
                left++;
            }
            while (left < right && height[right] <= h) {
                right--;
            }
        }

        return maxArea;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        Solution solution = new Solution();
        int result = solution.maxArea(height);
        System.out.println("Max area: " + result);
    }
}

package main

import "fmt"

func maxArea(height []int) int {
    n := len(height)
    maxArea := 0
    left, right := 0, n-1

    for left < right {
        h := min(height[left], height[right])
        area := h * (right - left)
        maxArea = max(maxArea, area)

        for left < right && height[left] <= h {
            left++
        }
        for left < right && height[right] <= h {
            right--
        }
    }

    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    height := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
    result := maxArea(height)
    fmt.Println("Max area:", result)
}

def maxArea(height):
    n = len(height)
    maxArea = 0
    left, right = 0, n - 1

    while left < right:
        h = min(height[left], height[right])
        area = h * (right - left)
        maxArea = max(maxArea, area)

        while left < right and height[left] <= h:
            left += 1
        while left < right and height[right] <= h:
            right -= 1

    return maxArea

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
result = maxArea(height)
print("Max area:", result)

function maxArea(height) {
    let n = height.length;
    let maxArea = 0;
    let left = 0, right = n - 1;

    while (left < right) {
        let h = Math.min(height[left], height[right]);
        let area = h * (right - left);
        maxArea = Math.max(maxArea, area);

        while (left < right && height[left] <= h) {
            left++;
        }
        while (left < right && height[right] <= h) {
            right--;
        }
    }

    return maxArea;
}

let height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
let result = maxArea(height);
console.log("Max area:", result);
取自“https://www.aigetting.com/index.php?title=题目:盛最多水的容器&oldid=2100”