知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 79 - 盛最多水的容器 ## 题目(LeetCode 11) 给定 n 条垂线,找出两条线与 x 轴构成的容器能盛最多的水。 ## 解法:双指针 ```java class Solution { public int maxArea(int[] height) { int left = 0, right = height.length - 1, res = 0; //从两头往中间挤 while (left < right) { int area = Math.min(height[left], height[right]) * (right - left); res = Math.max(res, area); //每次移动较矮的那一边 if (height[left] < height[right]) { left++; }else{ right--; } } return res; } } ``` ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 双指针从两端向中间收缩,每次移动较矮的那一边。 ## 为什么暴力是 O(n²) 暴力枚举所有 (i, j) 对,共 n*(n-1)/2 种组合,每次计算面积 O(1),总体 O(n²)。 ```java // 暴力(仅作对比,会超时) int maxArea = 0; for (int i = 0; i < height.length; i++) for (int j = i + 1; j < height.length; j++) maxArea = Math.max(maxArea, Math.min(height[i], height[j]) * (j - i)); ``` 双指针的正确性:当 `height[left] < height[right]` 时,以 left 为左边界的所有容器中,当前已是最大(right 最远),移动 left 才有可能找到更大的容器,移动 right 只会让宽度减小且高度不增。 ## 解法对比 | | 双指针 | 暴力枚举 | |--|--------|--------| | 时间复杂度 | O(n) | O(n²) | | 空间复杂度 | O(1) | O(1) | | 特点 | 最优,基于贪心证明 | 简单但超时 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入