題目描述

題目分析

看到題目后第一個想法當然是$O(n^2)$的，但是數據范圍是3e4，應該會超時，而且這種數據范圍也不是讓暴力求解的 。

相當于求解${\sum }_{i<j}max((j?i)?min(a[i],a[j]))$。因為$min$的緣故，所以我覺得不能進行區間合并。總之沒有什么頭緒。

看了題解以后發現這是一道數學題，策略： 初始時用兩個指針一個指向左側，一個指向右側，每次記錄當前容量，并將較小指針向較大指針移動。

證明：后附

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int i = 0, j = n - 1;int ans = 0;while (i < j) {if (height[i] < height[j]) {ans = max(ans, height[i] * (j - i));++i;} else {ans = max(ans, height[j] * (j - i));--j;}}return ans;}
};