当前位置: 首页 > news >正文

【算法专题】双指针—盛最多水的容器

一、题目解析

 

分析这个题目不难得出一个容积公式

 

二、算法原理

解法一:暴力枚举(超时)

套用上述的容积公式,使用两个for循环来枚举出所有可能的情况,再挑出最大值即可,但是这种写法会超时,导致不通过。时间复杂度是O(n^2)

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int ret = 0;    for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {ret = max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};

可以自己去尝试一下。 

解法二:双指针 

设两个指针left,right分别为这个容器的左边界和右边界,根据容积公式可得

v = min( height[right], height[left]) * (right - left)

从题目中的测试用例中选取一段进行分析如下:

所以我们可以得出结论用较小的数向内枚举的话容积肯定是在减小的,所以较小的数我们就可以不用向后枚举了直接跳过,用较大的数向后枚举就行。 

最后选出容积最大值就行了。 时间复杂度是O(n)。

三、代码编写

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while(left < right){int v = min(height[left],height[right]) * (right - left);ret = max(ret, v);if(height[left] < height[right]){left++;}else {right--;}}return ret;}
};
http://www.lryc.cn/news/214557.html

相关文章:

  • java入门,程序=数据结构+算法
  • 9.MySQL索引的操作
  • 大型加油站3d全景虚拟现实展示平台实现全方位立体呈现
  • Reading:Deep dive into the OnPush change detection strategy in Angular
  • 野火霸天虎 STM32F407 学习笔记_1 stm32介绍;调试方法介绍
  • @reduxjs/toolkit配置react-redux解决createStore或将在未来被淘汰警告
  • 致敬1024天前的自己
  • 〖Python网络爬虫实战㊱〗- JavaScript 网站加密和混淆
  • 基于单片机设计的电子柜锁
  • Windows安装tensorflow-gpu=1.14.0CUDA=10.0cuDNN=7.4 (多版本CUDA共存)
  • CodeWhisperer 初体验
  • HNU-算法设计与分析-讨论课1
  • java连接zookeeper
  • 2023-11-01 node.js-electron-环境配置-记录
  • 使用 ElementUI 组件构建 Window 桌面应用探索与实践(WinForm)
  • 使用C++构建安全队列
  • EasyFlash移植使用- 关于单片机 BootLoader和APP均使用的情况
  • python捕获异常和scapy模块的利用
  • CSS+Javascript+Html日历控件
  • 让企业的数据用起来,数据中台=数据治理?
  • 【人工智能Ⅰ】5-粒子群算法
  • 软考高项-49个项目管理过程输入、输出和工具技术表
  • 《C和指针》(7)函数
  • vue3中的Props
  • ElasticSearch搜索技术深入与聚合查询实战
  • vue+element ui中的el-button自定义icon图标
  • PyQt5:构建目标检测算法GUI界面 (附python代码)
  • SV-10A-4G IP网络报警非可视终端 (4G版)
  • 对xml文本元素赋值
  • 【k8s】资源管理命令-陈述式