LeetCode 11: Container With Most Water

发布时间:2014-10-22 14:23:14编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode 11: Container With Most Water",主要涉及到LeetCode 11: Container With Most Water方面的内容,对于LeetCode 11: Container With Most Water感兴趣的同学可以参考一下。

Difficulty: 3 Frequency: 2 Problem: 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. Solution: class Solution { public: int maxArea(vector<int> &height) { // Start typing your C/C++ solution below // DO NOT write int main() function if (height.size()<2) return 0; int i_start = 0, i_end = height.size() - 1; int i_area = (height[i_start]<height[i_end]?height[i_start]:height[i_end])*(i_end - i_start); int i_temp_area = 0; while(i_start<i_end) { if (height[i_start]<height[i_end]) ++i_start; else --i_end; i_temp_area = (height[i_start]<height[i_end]?height[i_start]:height[i_end])*(i_end - i_start); i_area = i_area>i_temp_area?i_area:i_temp_area; } return i_area; } }; Notes: Originally, I misunderstood this problem. This algorithm is borrowed from other. Time complexity is O(n). Another thing is that when (height[i_start] == height[i_end]), move either i_start or i_end is OK.

下一篇:(step7.2.3)hdu 2554(N对数的排列问题——简单数论)