前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >盛水最多的容器问题

盛水最多的容器问题

作者头像
用户11458826
发布2025-01-23 17:02:26
发布2025-01-23 17:02:26
2900
代码可运行
举报
文章被收录于专栏:杀马特
运行总次数:0
代码可运行

一·题目概述:

leetcode链接:. - 力扣(LeetCode)

二·思路理解:

首先这道题虽然看起来简单,很难不让人想到直接暴力破解它,但是直接就被leetcode判断超时了。因此需要调换更加巧妙的方法了,这样用的是双指针从两头筛选去遍历,时间复杂度是o(n^2)。

大致思路:

代码语言:javascript
代码运行次数:0
复制
v=w*h,因此可以使用两端指针,边走,边判断,边舍弃
在两端先保存记录一个v,这个h是以数值最小的为准,故当拿最小的往里面遍历,首先w一定减小,而当遇到比它数值小的则以那个小的为基准,
如果遇到比它大的,那就以它为基准,但是最终还是比原来保存的v小,故总结的规律就是,可以舍弃这个左右指针对应的比较小的那个数值,知道相遇
返回保存记录的最大的v

下面画图来理解一下:

三·解答代码:

代码语言:javascript
代码运行次数:0
复制
class Solution {
public:
    int maxArea(vector<int>& height) {
      int left=0,right=height.size()-1,ret=0;
       while(left<right){
           int high=min(height[left],height[right]);
           int volume=high*(right-left);
           ret=max(ret,volume);
           if(height[left]<height[right]) left++;//要点
           else  right--;
       }
       return ret;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一·题目概述:
  • 二·思路理解:
  • 三·解答代码:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档