【LeetCode】【Python解读】Container with most water
2024-09-09 11:51:49
这个问题是芭芭拉在采访中遇到的,不幸的是,的复杂性O(n2)该,太失望了,难怪没有通过面试。
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.
题目说的有点复杂,大意是利用x轴作底,两个随意的竖直线段作杯壁,何时盛水最多。
木桶原理大家肯定都知道,水盛多少取决于最短的杯壁,所以此题还能够引申为往围成的区域内放矩形。如何使得矩形面积最大。
题目中的不能倾斜(slant:倾斜,倾倒)相应为矩形必须水平放置。
复杂度为O(n)的思想是贪心原理,先从底边最大的情况考虑,计算最大面积后。此时要将底边长度减1,仅仅须要将杯壁较短的那一边移动一个单位距离,得到的解必然优于杯壁较长那边移动的情况。这样保证每次移动都得到的是局部最优解。
class Solution {
public:
int maxArea(vector<int> &height) {
int Len = height.size(),low=0,high=Len-1;
int maxV = 0;
while(low<high){
maxV = max(maxV,(high-low)*min(height[low],height[high]));
if (height[low]<height[high]) low++;
else high--;
}
return maxV;
}
};
版权声明:本文博客原创文章,博客,未经同意,不得转载。
最新文章
- 升级python
- 随便写一下看下效果。一个js问题
- 【Cocos2d-x 3.x】屏幕自适应匹配
- 如何自学Android
- java设计模式(八) 适配器模式
- pythonchallenge之C++学习篇-02
- Oracle自动统计信息的收集原理及实验
- iOS 2D绘图详解(Quartz 2D)之阴影和渐变(Shadow,Gradient)
- 李洪强漫谈iOS开发[C语言-007]-语言标准简介
- Android(java)学习笔记202:Handler消息机制的原理和实现
- viewDidLoad、viewDidUnload、viewWillAppear、viewDidAppear、viewWillDisappear 和 -viewDidDisappear的区别和使用
- UPX 加壳工具:The Ultimate Packer for eXecutables
- 【转载】Stack Overflow: The Architecture - 2016 Edition
- 基于数据库的自动化生成工具,自动生成JavaBean、自动生成数据库文档等(v4.1.2版)
- Tsung测试Tcp协议的应用或接口
- 部署上次的Hapi到Windows+Docker,WindowsDocker
- Python_实现json数据的jsonPath(精简版)定位及增删改操作
- numpy中的随机数模块
- poi的cellstyle陷阱,样式覆盖
- 伪分布式hbase2.6.5和hbase1.1.2的配置