leetcode11：盛最多水的容器

题目链接

leetcode

题目描述

给定一个长度为 n 的整数数组height 。
有 n 条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：不能倾斜容器。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]" <<endl;
}

/*
    暴力解法

    双重循环：
        使用双重循环枚举所有可能的两个柱子组合。
        外层循环从第 i 个柱子开始，内层循环从第 i+1 个柱子开始。
    计算面积：
        对于每对柱子，计算它们之间的面积：min(height[i], height[j]) * (j - i)。
        更新最大面积。
    
    时间复杂度：O(n^2)
        时间复杂度为 O(n^2)，其中 n 是数组的长度。
        每对柱子之间的面积计算需要 O(1)，总共有 O(n^2) 对柱子。
    空间复杂度：O(1)
        空间复杂度为 O(1)，因为只使用了常量级的额外空间。
*/
class Solution_0 {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int maxArea = 0;

        // 枚举所有可能的两个柱子组合
        for (int i = 0; i < n; i ++) {
            for (int j = i + 1; j < n; j ++) {
                // 计算当前两个柱子之间的面积
                int area = min(height[i], height[j]) * (j - i);
                // 更新最大面积
                maxArea = max(maxArea, area);
            }
        }

        return maxArea;
    }
};

/*
	接雨水问题给出的类似一幅直方图，每个横坐标都有宽度；
	而本题给出的每个坐标是一条竖线，没有宽度。
	接雨水问题更难一些，每个坐标对应的矩形通过左右最大高度的最小值推算自己能装多少水。
	
	本题使用接雨水问题的思路：
        left 和 right 两个指针从两端向中心收缩，
        一边收缩一边计算 [left, right] 之间的矩形面积，取最大的面积值即是答案。
        矩形的高度是由较低的一边决定的，即 min(height[left], height[right])。
	
	时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int left = 0, right = height.size() - 1;
        while (left < right) {
            // [left, right] 之间的矩形
            int area = min(height[left], height[right]) * (right - left);
            res = max(res, area);
            if (height[left] < height[right]) left ++;
            else right --;
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> testCases = {
        {1,8,6,2,5,4,8,3,7},
        {1,1}
    };

    for (auto& nums : testCases) {
        cout << "Input: ";
        printArray(nums);
        cout << "Output: " << solution.maxArea(nums) << endl;
    }
    
    return 0;
}

Golang 代码

package main

import "fmt"

/*
   使用两个指针，一个从数组的开头，一个从数组的结尾，逐渐向中间移动。
   在每次移动时，计算当前指针所围成的矩形的面积，并更新最大面积。
   根据两个指针所指向的高度，将较短的指针向中间移动一步，继续计算面积，直到两个指针相遇。

   时间复杂度：O(n)
       其中 n 是数组的长度。
       两个指针从数组的两端向中间移动，每个指针最多移动 n 次。
   空间复杂度：O(1)
       只使用了固定的几个变量。
*/
func maxArea(height []int) int {
    maxArea := 0
    left, right := 0, len(height)-1
    for left < right {
        w := right - left
        h := min(height[left], height[right])
        area := w * h
        if maxArea < area {
            maxArea = area
        }
        if height[left] < height[right] {
            left ++
        } else {
            right --
        }
    }

    return maxArea
}

func main() {
    // 测试用例
	testCases := []struct {
		height   []int
		expected int
	}{
		{[]int{1,8,6,2,5,4,8,3,7}, 49},
		{[]int{1,1}, 1},
	}

	for i, tc := range testCases {
		result := maxArea(tc.height)
		fmt.Printf("Test Case %d, Input: height = %v\n", i+1, tc.height)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}