【Container With Most Water】cpp
2024-10-20 08:24:19
题目:
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.
代码:
class Solution {
public:
int maxArea(vector<int>& height) {
if ( height.size()< ) return ;
int max_area = ;
int left = ;
int right = height.size()-;
while ( left<right )
{
if ( height[left]<=height[right] )
{
max_area = std::max(max_area, (right-left)*height[left]);
left++;
}
else
{
max_area = std::max(max_area, (right-left)*height[right]);
right--;
}
}
return max_area;
}
};
tips:
试图用DP去做,但是没想出来;最后无奈落入了Greedy的俗套solution。
这个greedy的思路也是蛮巧的:从两头开始往中间greedy,头尾两个greedy一起变化才得到greedy的条件。
=======================================
第二次过这道题,这道题题意不清晰:如果选了某两个板子,就当其他板子不存在。
class Solution {
public:
int maxArea(vector<int>& height) {
int l = ;
int r = height.size()-;
int ret = ;
while ( l<r )
{
if ( height[l]<=height[r] )
{
ret = max(ret, (r-l)*height[l]);
l++;
}
else
{
ret = max(ret, (r-l)*height[r]);
r--;
}
}
return ret;
}
};
最新文章
- SQLite3
- 【JavaScript】浅析javaScript和HTML与unicode字符集的关系
- 【翻译】ASP.NET MVC 5属性路由(转)
- spring security使用数据库资源
- HTTPS Everywhere – 保障隐私和信息安全的利器
- 利用powerdesigner反向数据库结构,生成ER图
- 【OpenMesh】Some basic operations: Flipping and collapsing edges
- c++ 使用全局变量的方法多个文件
- Spring Security 3.2.x与Spring 4.0.x的Maven依赖管理
- (GO_GTD_1)基于OpenCV和QT,建立Android图像处理程序
- 【Html5】-- 塔台管制
- zookeeper安装以及遇到的一些坑
- 12.JavaScript字符串方法
- PA教材提纲 TAW12-2
- 移植 Qt 至 tiny210 详细过程
- 黄聪:php7配置php.ini使其支持<;? ?>;
- Ajax技术剖析
- Linux系统软件包的管理(4)
- MySql 按周/月/日统计数据的方法
- windows7无声音,提示未插入扬声器或耳机的解决