LC11 盛最多水的容器
选择两条线,它们与x轴构成的容器可以盛的水量取决于两条线中较短的那条以及两条线之间的距离。

朴素的思想是使用ij遍历height中的所有线,但是这样的时间复杂度是O(n2)O(n^2)O(n2)

我们让i0开始,jn-1开始,组成一个容器。
在这里插入图片描述
不妨假设height[0]<=height[n-1],则固定左端点组成的所有容器中,无论右端点在哪,容器的盛水高度不可能高过左端点的线高,故初始容器就是固定左端点组成的所有容器中盛水量最多的容器。这里本质上把固定左端点对右端点进行O(n)O(n)O(n)的扫描通过分析变成了O(1)O(1)O(1)

i=0的情况看完了,接下来应该移动左端点i。这里本质上是在固定右端点对左端点进行扫描。我们将左端点移动到比初始线高更高的第一个位置,则组成容器的盛水高度会变高,才有可能盛水量更多。则容器左端点从初始的i=0到现在位置中的所有左端点,其右端点一直保持j=n-1,因为不需要扫描,对于这些左端点,移动右端点不会使得盛水量更多。这里的分析就是算法的时间复杂度下降的原因。我们只需要分析如何让容器向着盛水量可能变大的方向去变化,每次移动较矮侧的端点至下一个更高位置处即可。

最终容器的变化过程就是,每次让容器较矮的一侧变的更高,直到两个端点重合。这样时间复杂度就是左右端点共同扫描完原数组,即O(n)O(n)O(n)

这里我们对完备性进行一些简单证明。我们算法移动左右端点的过程中不会固定某一个端点对另一个端点进行O(n)O(n)O(n)的扫描都是因为通过分析可知,当我们在移动一侧的过程中,没有移动的那一侧无论取在哪也不会使得盛水量变大,所以盛水量最多的情形只要其左端点或者右端点作为过我们算法移动过程中的对应左端点或右端点,则我们的算法一定会得到不小于盛水量最多情形的结果。而由于那又是盛水量最多的情形,所以不小于即为等于。

class Solution {public int maxArea(int[] height) {int left=0,right=height.length-1,ans=0;while(left<right){ans=Math.max(ans,Math.min(height[left],height[right])*(right-left));if(height[left]<=height[right]){int std=height[left];//让left向右移动到一个更高的位置for(;left<right;left++){if(height[left]>std) break;}}else{int std=height[right];//让right向左移动到一个更高的位置for(;right>left;right--){if(height[right]>std) break;}}}return ans;}
}

这里的ij就是双指针,从两侧向中间收拢,每次变化都向着可能使得盛水量变大的方向变化,且每次变化的特点是容器的盛水高度更高,宽度更小。这一题的变化过程分析对LC42 接雨水的解题有帮助。

LC42 接雨水
这道题也可以一样使用从两侧向中间收拢的双指针。我们下图中的线实际是一个宽度为1的柱子,这里画图简化了。
在这里插入图片描述
我们记minH为当前两个端点柱子高度的较小值,一开始让i=0j=n-1lastH为地面高度为0。则初始状态可以计算出lastHminH高度之间的雨水量。

不妨假设height[0]<=height[n-1],则无论怎么移动右端点,i=0高于minH的部分都不会有雨水,这点和LC11中的容器很像。所以对于i=0的部分,不需要花费O(n)O(n)O(n)去遍历右端点j,这时应该直接移动左端点i至下一个更高的柱子处,找到积水高度更高的“容器”。找到后,更新minH的值,并将原本minH的值给lastH,计算雨水量的增量是新的minH和最初minH即当前lastH之间的雨水,且容易反证在当前左端点左侧高于初始minH的部分不可能有雨水,这点和LC11中的容器也很像,因为该部分不属于新容器的范围。

这样我们一样是以O(n)O(n)O(n)的时间复杂度遍历了所有可能有雨水的左右端点情形,以朴素的思想,会在每个我们更新更高柱子的“容器”中遍历中间的每个宽度计算当前ij宽度之间、当前lastHminH高度之间的雨水量,这样总时间复杂度是O(n2)O(n^2)O(n2),不是最优。

接下来需要再利用一定的分析技巧去降低时间复杂度,我们不要在每次“容器”改变形状时去遍历宽度计算雨水。我们有如下发现,以我们的左端点来看,我们会让左端点i0变化到下一个更高柱子处,然后继续到下一个更高的柱子处,所有的雨水不会出现在每一个更高的柱子处,只会出现在我们移动左端点前后的中间的柱子处,且雨水高度也均为移动前的minH。所以我们有更聪明的计算雨水的方法,每次移动端点时,计算该端点处的雨水量(minH-height[i],以左端点为例),而不再每次去遍历宽度计算“容器”内的lastHminH高度之间的雨水量。这样总时间复杂度就被优化至O(n)O(n)O(n)

class Solution {public int trap(int[] height) {int n=height.length,i=0,j=n-1;int minH,ans=0;while(i<j){minH=Math.min(height[i],height[j]);//i和j处较矮者向中间移动,移动至更高处停止//每次移动,计算移动的那个宽度的雨水量if(height[i]<=height[j]){for(;i<j&&height[i]<=minH;i++){ans+=minH-height[i];}}else{for(;i<j&&height[j]<=minH;j--){ans+=minH-height[j];}}}return ans;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/95033.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/95033.shtml
英文地址,请注明出处:http://en.pswp.cn/bicheng/95033.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

WINTRUST!_GetMessage函数分析之CRYPT32!CryptSIPGetSignedDataMsg函数的作用是得到nt5inf.cat的信息

UEDIT打开nt5inf.cat。第一部分&#xff1a;BOOL _GetMessage(CRYPT_PROVIDER_DATA *pProvData) {DWORD dwMsgEncoding;SIP_SUBJECTINFO *pSubjInfo;SIP_DISPATCH_INFO *pSip;DWORD cbEncodedMsg;BYTE *pbEncodedMsg;DWORD …

编译esp32报错解决办法

报错信息&#xff1a;CMake Error at build/CMakeFiles/git-data/grabRef.cmake:48 (file):file failed to open for reading (No such file or directory):这个错误是由于 Git 的安全检查导致的。从错误信息可以看出&#xff0c;Git 检测到了"可疑的所有权"&#xf…

【AI】常见8大LLM大语言模型地址

序号AI名称地址1 ChatGPT &#xff08;OpenAI&#xff09;https://chat.openai.com/2Gemini (Google personal AI assistant)https://gemini.google.com/app3Grok (xAI Grok LLM)https://x.ai/4DeepSeek (DeepSeek AI chatbot)DeepSeek5Claude (Anthropic Claude AI)App unavai…

软件系统的部署方式:单机、主备(冷主备、热主备)、集群

一、单机部署单机部署是将软件系统所有组件&#xff08;应用、数据库等&#xff09;部署在单台服务器上&#xff0c;架构简单、成本低但存在单点故障风险&#xff0c;适用于低负载或测试场景。一台服务器坏了&#xff0c;软件系统无法服务。二、主备&#xff08;冷主备、热主备…

从体验到系统工程丨上手评测国内首款 AI 电商 App

作者&#xff1a;王晨&#xff08;望宸&#xff09; 产品界面&#xff0c;往往体现了产品的设计哲学&#xff0c;界面是产品的第一入口。 近期&#xff0c;1688 推出了 1688 AI App&#xff0c;这貌似是国内第一个电商领域的独立 AI App 应用&#xff08;若不是&#xff0c;欢…

QML QQuickImage: Cannot open: qrc:/images/shrink.png(已解决)

此问题是 在 QT Quick 项目 显示图片的时候 遇到&#xff0c;显示&#xff1a;QML QQuickImage: Cannot open: qrc:/images/shrink.png&#xff0c;不能 打开 图片。为了解决此问题&#xff0c;找了很多资料&#xff0c;虽然是比较简单&#xff0c;但对于初学者来说&#xff0c…

maven scope 详解

Maven 的 scope用于定义依赖项在项目构建生命周期中的可见性和传递性&#xff0c;控制依赖在编译、测试、运行等阶段的可用性及是否被打包到最终产物中。以下是详细解析&#xff1a;⚙️ ​​一、Scope 的核心作用​​​​生命周期控制​​决定依赖在编译、测试、运行阶段的可用…

Python的一次实际应用:利用Python操作Word文档的页码

Python的一次实际应用&#xff1a;利用Python操作Word文档的页码 需求&#xff1a;一次性处理24个文档的页码。 文档详情&#xff1a; 1、每个word文档包含800页左右&#xff0c;每一页包含一个标题和一张图片。 2、由于图片有横排也有竖排&#xff0c;因此&#xff0c;每页文档…

Android15 GKI版本分析Kernel Crash问题

环境介绍编译主机&#xff1a;amd64 Ubuntu 22.04Android源码&#xff1a;Android15 GKIKernel版本&#xff1a;Linux 6.16Android构建系统&#xff1a;bazel构建工具链&#xff1a;gcc-arm-10.3-2021.07-x86_64-aarch64-none-linux-gnu/bin/aarch64-none-linux-gnu-定位Linux…

rocky 9部署Zabbix监控

一、rocky安装 需要注意在设置root用户密码时&#xff0c;勾选ssh远程连接 安装完成后直接用root登录 1. 网络配置 输入nmtui 进入网络配置界面 选择 Edit a connection&#xff0c;再选择接口 ens3 IPV4更改为Maual 手动模式 根据实际环境配置IP地址 重启网络 systemctl …

从9.4%到13.5%:ICDM2025录取率触底反弹,竞争压力稍缓

近日&#xff0c;ICDM 2025公布了论文录用结果。本次大会共收到785篇有效论文投稿&#xff0c;最终&#xff0c;共有106篇常规论文和70篇短论文被接收&#xff0c;总体接收率为22.4%&#xff0c;其中全文论文的接收率为13.5%。与前年9.4%、去年11.09%的录取率相比&#xff0c;I…

linux上安装methylkit -- 安全下车版 (正经版: Linux环境下安装methylKit的实践与避坑指南)

题外话&#xff1a; 我踩过的坑&#xff0c;都将成为我写贴的素材&#xff01;(ㄒoㄒ) 整整安装了两天&#xff0c;这里面的滋味懂的都懂。 希望开发作者持续维护。 希望有人或者作者持续打包成sigularity镜像使用&#xff0c;并且直接传到github上&#xff0c;传到docker上下…

【leetcode】114. 二叉树展开为链表

文章目录题目题解1. 递归2. 迭代3. 右指针重排&#xff0c;始终将右子树添加到左子树的最右题目 114. 二叉树展开为链表 题解 1. 递归 先序遍历然后将数组操作 for i in range(1, len(res)):prev, curr res[i - 1], res[i]prev.left Noneprev.right curr# Definition fo…

Vibe Coding、AI IDE/插件

概述 Vibe Coding&#xff0c;氛围编程&#xff0c;AI辅助编程&#xff0c;三剑客&#xff1a; Google Gemini&#xff1a;OpenAI GPT&#xff1a;Anthropic Claude&#xff1a; IDE Cursor 基于VS Code开发。 特性&#xff1a; AI驱动的代码生成&#xff1a;输入想要的…

Unity高级UI拖动控制器教程

在游戏开发过程中&#xff0c;UI组件的拖动功能是一个常见的需求。特别是在需要实现拖动、边界检测、透明度控制以及动画反馈等功能时&#xff0c;编写一个高级UI拖动控制器将非常有用。在本文中&#xff0c;我们将创建一个支持多种Canvas模式和更精确边界检测的高级UI拖动控制…

零基础上手:Cursor + MCP 爬取 YouTube 视频数据

前言 大模型与 AI 应用越来越普及的今天&#xff0c;实时、稳定地获取网络数据变得尤为重要。无论是做内容分析、趋势研究还是自动化任务&#xff0c;爬取和处理数据始终是绕不开的一环。 传统爬虫往往面临封禁、验证码、动态渲染等难题&#xff0c;而 Bright Data MCP&#x…

frp 一个高性能的反向代理服务

文章目录项目概述核心特性系统架构快速开始1. 下载安装2. 服务端快速配置3. 客户端快速配置4. 验证连接配置文件说明代理类型TCP/UDP 代理HTTP/HTTPS 代理安全代理 (STCP/SUDP)P2P 代理 (XTCP)插件系统静态文件服务HTTP/SOCKS5 代理协议转换使用场景远程办公Web 服务发布游戏服…

Android -第二十一次技术总结

一、activity与Fragment的通信有哪些&#xff1f;使用接口进行通信的逻辑与代码示例使用接口通信的核心是解耦&#xff0c;通过定义一个接口作为通信契约&#xff0c;让 Fragment 不依赖于具体的 Activity 类型。1. 定义通信接口&#xff08;在 Fragment 内&#xff09;首先&am…

【算法】78.子集--通俗讲解

通俗易懂讲解“子集”算法题目 一、题目是啥?一句话说清 给你一个不含重复元素的整数数组,返回所有可能的子集(包括空集和它本身)。 示例: 输入:nums = [1,2,3] 输出:[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]] 二、解题核心 使用回溯法(递归)或位运算来…

Cherrystudio的搭建和使用

1、下载和安装 Cherry Studio 官方网站 - 全能的 AI 助手 2、配置LLM 3、聊天助手 3.1 添加和编辑助手 3.2 选择LLM 3.3 对话聊天 4、配置MCP 4.1 安装MCP执行插件 4.2 安装 node和npm Node.js — Download Node.js npm -v 10.9.3 node -v v22…