LeetCode 11 Container With Most Water

2019-11-06 07:11:54

字体：大中小

来源：转载

供稿：网友

题目

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 and n is at least 2.

解法

看题看了好半天Orz。给定n个数，分别代表n条线段的高度，第i条线段的两个端点是(i,0)和(i,ai)，这些线段都是垂直于x轴的，选取其中的两条线段，使这两条线段和x轴构成的容器能容纳的水最多，装水的多少取决于两条线段中较短的那根线段。解题思路：从左右两边向中间逼近计算最大容水量。先选取两端的两条线段，这样两条线段之间的距离也就是宽度是最大的。在这种情况下要容纳更多的水，就要考虑提高线段的高度，如果两条线段是左边比右边高，将左边的指针右移，否则将右边的指针左移，这样不断移动直到指针重叠。用示意图演示下：

这里写图片描述

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

上一篇：【九度OJ】题目1201：二叉排序树解题报告

下一篇：CSDN模板