Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
Array Two Pointers
#include <iostream> #include <vector> using namespace std; #define MIN(l,r) ((l)<(r)?(l):(r)) class Solution { public: int maxArea(vector<int> &height) { int n = height.size(); if(n<2) return 0; if(n==2) return MIN(height[0],height[1]); int lidx=0,ridx=n-1,sum=0; while(lidx<ridx){ if(sum<(ridx-lidx)*MIN(height[lidx],height[ridx])) sum = (ridx-lidx)*MIN(height[lidx],height[ridx]); if(height[lidx]<height[ridx]) lidx++; else ridx--; } return sum; } }; int main() { vector<int > h{1,2,1}; Solution sol; cout<<sol.maxArea(h)<<endl; return 0; }
[LeetCode] Container With Most Water
原文：http://www.cnblogs.com/Azhu/p/4355052.html