[LeetCode] Container With Most Water(正确的算法)1
需积分: 0 124 浏览量
2022-08-08
19:02:22
上传
评论
收藏 20KB DOCX 举报
[LeetCode] Container With Most Water
Given n non-negative integers a
1
, a
2
, ..., a
n
, where each represents a
point at coordinate (i, a
i
). n vertical lines are drawn such that the two
endpoints of line i is at (i, a
i
) 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.
类似于 2Sum 的思想，两边设一个指针，然后计算 area，如果 height[i] <=
height[j]，那么 i++，因为在这里 height[i]是瓶颈，j 往里移只会减少面积，
不会再增加 area。
这是一个贪心的策略，每次取两边围栏最矮的一个推进，希望获取更多的水。
一个不严格的证明：
当 height[i] <= height[j]时，为什么是 i++，而不是 j++来获取可能更多的
水？
假设 j' > j，之所以 j'往左移，是因为存在 height[i'] > height[j'] (i’ <= i), 而
那时 area' = (j' - i') * min(height[i'], height[j'])，
因为 height[j'] == min(height[i'], height[j'])，所以 area' = (j' - i') *
height[j']。
而 i 和 j'构成的面积 area = (j' - i) * min(height[i], height[j'])。
area' >= area，所以 j 不需要往右移。
1 class Solution {
2 public:
3 int maxArea(vector<int> &height) {
4 // Start typing your C/C++ solution below
5 // DO NOT write int main() function
6 int i = 0;
7 int j = height.size() - 1;
8
9 int ret = 0;
资源评论
ali-12
- 粉丝: 28
- 资源: 328
最新资源
- 论文(最终)_20240430235101.pdf
- 基于python编写的Keras深度学习框架开发，利用卷积神经网络CNN,快速识别图片并进行分类
- 最全空间计量实证方法（空间杜宾模型和检验以及结果解释文档）.txt
- 5uonly.apk
- 蓝桥杯Python组的历年真题
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 前端开发技术实验报告：内含4四实验&实验报告
- Highlight Plus v20.0.1
- 林周瑜-论文.docx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
