leetcode11：盛最多水的容器

题目链接

leetcode

题目描述

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

C++ 代码

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

/*
    暴力解法

    两层循环：
        两层循环枚举所有可能的两个柱子组合。
        外层循环从第 i 个柱子开始，内层循环从第 i+1 个柱子开始。
    计算面积：
        对于每对柱子，计算它们之间的面积：min(height[i], height[j]) * (j - i)。
        更新最大面积。
    
    时间复杂度：O(n^2)
        时间复杂度为 O(n^2)，其中 n 是数组的长度。
        每对柱子之间的面积计算需要 O(1)，总共有 O(n^2) 对柱子。
    空间复杂度：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;
    }
};

/*
    i 和 j 两个指针从两端向中心收缩，
    收缩的同时计算 [i, j] 之间矩形的面积，取最大的面积值即是答案。
    矩形的高度是由较低的一边决定的，即 min(height[i], height[j])。
	
	时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int i = 0, j = height.size()-1;

        while (i < j) {
            int area = min(height[i], height[j]) * (j - i);
            res = max(res, area);
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

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

    for (auto& nums : height_cases) {
        int result =  solution.maxArea(nums);

        cout << "Input: ";
        printArray(nums);
        cout << endl;
        cout << "Output: " << result << endl;
    }
    
    return 0;
}