题解
这一题很经典,难吗?,想得到还是挺简单的。
该题的正解是 双指针 + 贪心 的策略,在其首尾各放一个指针,每次移动指针指向高度较小的数向内侧移动,在不断移动的过程中记录Max即可。
为何能保证得到最优解呢?
以图示验证算法的正确性:
这里采用反证法,先表示出最大区域面积,然后我们假设一个边长,倘若 L(右) > L(左),那么最大面积一定大于我们所表示出来的最大面积,但这很显然不成立,所以必须满足 L(右) < L(左),此时右边指针就会向左移动寻找一个比之前较大的高度。
算法时间复杂度可以控制在 $O(n)$ 以内。
class Solution { typedef long long LL; public: int maxArea(vector<int>& height) { // 双指针算法 int l = 0, r = height.size() - 1; LL maxx = 0; while (l < r) { maxx = max(maxx, (LL) (r - l) * min(height[l], height[r])); // 记录下来 int height1 = height[l]; int height2 = height[r]; if (height1 < height2) { ++l; while (l < r && height1 >= height[l]) ++l; } else { --r; while (l < r && height2 >= height[r]) --r; } } return maxx; } };