【题目】
Givennnon-negative integersa1,a2,
...,an, where each represents a point at coordinate (i,ai).nvertical
lines are drawn such that the two endpoints of lineiis 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.
【分析一】
最直接的思路是暴力枚举法,枚举容器的两个边。O(n^2)。超时。
【代码一】
/*********************************
* 日期:2015-01-21
* 作者:SJF0115
* 题目: 11.Container With Most Water
* 网址:https://oj.leetcode.com/problems/container-with-most-water/
* 结果:Time Limit Exceeded
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int maxArea(vector<int> &height) {
int count = height.size();
if(count <= 1){
return 0;
}//if
int maxArea = 0;
// 左边界
for(int i = 0;i < count-1;++i){
// 右边界
for(int j = i+1;j < count;++j){
int area = (j - i) * min(height[i],height[j]);
maxArea = max(area,maxArea);
}//for
}//for
return maxArea;
}
};
int main(){
Solution solution;
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
vec.push_back(1);
vec.push_back(4);
vec.push_back(2);
int result = solution.maxArea(vec);
// 输出
cout<<result<<endl;
return 0;
}
【分析二】
当从两边向中间考虑时,面积 = 两端较小的高度×两边之间的宽度。
假定初始的盛水面积为area=0,如果左边的高度小于右边的高度,容器左边向右运动一位。同理,如果右边的高度小于左边的高度,则向左运动一位。
【代码二】
/*********************************
* 日期:2015-01-21
* 作者:SJF0115
* 题目: 11.Container With Most Water
* 网址:https://oj.leetcode.com/problems/container-with-most-water/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int maxArea(vector<int> &height) {
int count = height.size();
if(count <= 1){
return 0;
}//if
int maxArea = 0,area = 0;
// 二分查找变形
for(int i = 0,j = count-1;i < j;){
// 去掉低的一边
if(height[i] > height[j]){
area = (j - i) * height[j];
--j;
}//if
else{
area = (j - i) * height[i];
++i;
}//else
// 更新最大面积
if(area > maxArea){
maxArea = area;
}//if
}//for
return maxArea;
}
};
int main(){
Solution solution;
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
vec.push_back(1);
vec.push_back(4);
vec.push_back(2);
int result = solution.maxArea(vec);
// 输出
cout<<result<<endl;
return 0;
}
【分析三】
当从两边向中间考虑时,面积 = 两端较小的高度×两边之间的宽度。
假定初始的盛水面积为area=0,如果左边的高度小于右边的高度,容器左边向右运动,直到找到一个比原先左边高度高的。
同理,如果右边的高度小于左边的高度,则向左运动,直到找到一个比原先右边高度高的。
【代码三】
class Solution {
public:
int maxArea(vector<int> &height) {
int count = height.size();
if(count <= 1){
return 0;
}//if
int index,maxArea = 0,area = 0;
// 二分查找变形
for(int i = 0,j = count-1;i < j;){
// 去掉低的一边
if(height[i] > height[j]){
area = (j - i) * height[j];
index = j;
// 向左移动,直到找到一个比height[index]高的
while(height[j] <= height[index]){
--j;
}//while
}//if
else{
area = (j - i) * height[i];
index = i;
// 向右移动,直到找到一个比height[index]高的
while(height[i] <= height[index]){
++i;
}//while
}//else
// 更新最大面积
if(area > maxArea){
maxArea = area;
}//if
}//for
return maxArea;
}
};
【分析四】
构建结构体包含height和height在原数组中的位置
struct Node
{
int height;
int index;
};
对该结构体数组按照height的值递增排序,假设排序后的数组为vec.
假设f[i] 表示数组vec[i,i+1,…]内所有height按照原来的位置顺序排列好以后的最大水量
那么f[i-1]可以在O(1)时间内计算出来:因为vec[i-1].height 小于vec[i,i+1,…]内的所有height,所以以vec[i-1].index为边界的容器高度为vec[i-1].height,最大水量只需要分别计算vec[i,i+1,…]内按原始位置排列最前面和最后面的height,取两者的较大值。即下图中,黑色是最低的,要计算以黑色为边界的容器的最大水量,只需要分别和第一个和最后一个计算,去两者较大值
【代码四】
class Solution {
struct Node
{
int height;
int index;
Node(int h, int i):height(h),index(i){}
Node(){}
bool operator < (const Node &a)const
{
return height < a.height;
}
};
public:
int maxArea(vector<int> &height) {
int res = 0, n = height.size();
if(n <= 1)return 0;
vector<Node>vec(n);
for(int i = 0; i < n; i++)
{
vec[i].index = i;
vec[i].height = height[i];
}
sort(vec.begin(), vec.end());
int start = vec[n-1].index, end = start;//记录已经处理完的height的原始位置的左右端点
for(int i = n-2; i >= 0 ; i--)
{
start = min(start, vec[i].index);
end = max(end, vec[i].index);
res = max(res, max(vec[i].height*(vec[i].index - start), vec[i].height*(end - vec[i].index)));
}
return res;
}
};
类似题目:
庞果网之寻找直方图中面积最大的矩形
LeetCode之Trapping Rain Water
分享到:
相关推荐
[LeetCode] Container With Most WaterGiven n non-negative integers a1, a2, ..., a
11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two...
/*中级思路以下我觉得分析有点问题*/ 中级思路, 这样的值 有两个性质, 不妨设 (i,a)为左边 (j,b)为右边为最大值, 1.若有坐标
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. ...
11.Container With Most Water 12.Integer to Roman 13.Roman to Integer 14.Longest Common Prefix (Trie树待完成) 15.3Sum 16.3Sum Closest 17.Letter Combinations of a Phone Number 18.4Sum 19.Remove Nth Node...
Leetcode回文串拼接 ...11.Container With Most Water 12.Integer To Roman 13.Roman To Integer 289 347 380 442 457 Circular Array Loop 535 Encode and Decode TinyURL 560 565 566 Maximum Binary T
lru cache leetcode #算法解题报告 ...11.Container With Most Water 14.Longest Common Prefix 15.3Sum 16.3Sum Closest 19.Remove Nth Node From End of List 20.Valid Parentheses 21.Merge Two Sorted L
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. ...
leetcode 跳跃 LeetCode Solved by Python easy/middle/hard:15/36/5 1. Two Sum 两数之和 2. Add Two Numbers 两数相加 3. Longest Substring Without Repeating Characters 无重复字符的最长子串 4. Median of ...
Container With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum...
leetcode 答案 LeetCode My LeetCode solution List 4. Longest Substring Without Repeating Characters: Using the dict[] to record the last position of each letter. 5. Longest Palindromic Substring: ...
with Ruby 13. Roman to Integer 查表,通过从前往前筛选字符串,把代表的值一个个加起来 26. Remove Duplicates from Sorted Array 难度easy的题目。根据题目要求,是不能新建数组。只能在原来的基础上做修改。基本...
11 Container With Most Water 这里题目的分析图如下: 所以我们需要找的是ai,aj中的最小值作为高,然后找(i-j)的最大值作为长 然后得到最大的容积。 所以我们这样做 用两个point来记录现在所在的x坐标(即i值) ...
leetcode数组下标大于间距 5. Longest Palindromic Substring 这里使用menecher方法,就是动态规划,首先在原先的字符串之间插入'#, 这样可以统一处理奇数串和偶数串, 使用两个变量纪录状态, far_pos表示最长回文...
Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 ...
收集面试中提出的一些重要问题。 数据结构算法面试问题面试中提出的一些重要问题的集合。 ...https://leetcode.com/problems/trapping-rain-water/ [解决方案] ...with-most-water/ htt
LC11_ContainerWithMostWater.py ├── LC121_BestTimetoBuyAndSellStock.py ├── LC12_IntToRoman.py ├── LC13_RomanToInt.py ├── LC144_BinaryTreePreorderTraversal.py ├── LC14_longestCommonPrefix...
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 英文题目 题目描述 JavaScript 难度 1 Two Sum 简单 2 Add Two Numbers 中等 3 Longest Substring Without Repeating... 中等 5...
指数姓名有效码无效的代码2个 3 4 5 6 7ReverseInteger.java 8 字符串到整数(atoi) StringToInteger.java StringToInteger(Invalid).java 11 装满水的容器ContainerWithMostWater.java 12 整数到罗马...