钓鱼网站如何做百度网站打不开

钓鱼网站如何做,百度网站打不开,广州邮局网站,怎么制作网站横幅在 LeetCode 的 Hot 100 题单中#xff0c;第 11 题“盛最多水的容器”是一道极具代表性的题目。它不仅考察编程技巧#xff0c;更考察通过数学逻辑优化算法的能力。这道题的暴力解法很容易想到#xff0c;但要达到 的最优复杂度#xff0c;需要利用双指针技巧。今天我们就…在 LeetCode 的Hot 100题单中第 11 题“盛最多水的容器”是一道极具代表性的题目。它不仅考察编程技巧更考察通过数学逻辑优化算法的能力。这道题的暴力解法很容易想到但要达到的最优复杂度需要利用双指针技巧。今天我们就来深入剖析这道题。1. 题目核心分析题目描述给定一个数组height数组中的每个元素代表一条垂直线的长度。找出两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。核心公式我们面临的是一个权衡问题想要面积大宽度距离要大。想要面积大高度短板也要高。但因为木桶效应容器的高度取决于两边较短的那条线。2. 为什么暴力法不可行最直观的想法是两层for循环枚举所有可能的组合(i, j)计算面积并取最大值。时间复杂度。数据范围题目提示。结果的平方是这远远超过了计算机 1 秒钟的处理能力约次运算会导致超时 (TLE)。因此我们需要寻找一种线性时间 $O(N)$ 的解法。3. 核心解法双指针 (Double Pointer)算法流程我们采用“缩减搜索空间”的策略。初始状态定义两个指针left指向数组开头right指向数组结尾。此时宽度最大。计算面积计算当前left和right围成的面积更新最大值maxArea。移动策略关键如果height[left] height[right]移动左指针(left)。如果height[left] height[right]移动右指针(right--)。口诀谁短动谁。终止条件当left和right相遇时停止。为什么是“谁短动谁”直观理解假设现在left处的线比right处的线短。如果不移动left短板而是移动right长板宽度一定变小。高度受限于left短板。无论right移过来的新线有多高整个容器的高度绝不可能超过left的高度。如果新线比left还矮高度甚至会更低。结论宽度变小高度不变或变小面积一定变小。这意味着只要left是短板这一轮以left为边界的所有情况left和任意right的组合中最开始算的那次最远距离就是最大的。left已经没有利用价值了所以我们丢弃left尝试找一根更高的线。4. 严谨的数学证明如果你觉得直观理解不够严谨我们来看一下数学推导。假设当前左右指针分别为和且左边是短板。当前的距离为。当前面积。证明为什么要移动我们要证明的是在保留的情况下无论 $R$ 向左移动到任何位置()得到的面积一定小于等于。新的宽度显然。新的高度。因为高度由短板决定所以恒成立。新面积。因为且。所以恒成立。结论只要确定了是短板那么与右边任意一条线的组合最大面积只能是当前算出来的这个。因此我们可以安全地排除去探索新的可能性。5. 代码实现 (Java)Javaclass Solution { public int maxArea(int[] height) { // 定义双指针分别指向头尾 int l 0, r height.length - 1; int ans 0; while (l r) { // 1. 计算当前面积 // 高度由短板决定 int currentHeight Math.min(height[l], height[r]); // 宽度是索引差 int currentWidth r - l; int area currentHeight * currentWidth; // 2. 更新最大面积 ans Math.max(ans, area); // 3. 移动策略谁短动谁 // 移动短板是为了试图找到更高的板子从而可能抵消宽度的减小 if (height[l] height[r]) { l; } else { r--; } } return ans; } }6. 复杂度分析时间复杂度:双指针l和r总共遍历整个数组一次。每个元素最多被访问一次。空间复杂度:只需要存储l,r,ans等几个变量不需要额外的数组空间。7. 总结LeetCode 11 题是贪心思想与双指针结合的典范。解决此题的关键在于打破“遍历所有组合”的思维定势转而思考什么情况下我们能确定一条边已经发挥了最大潜力可以被安全地“丢弃”Wood Bucket Theory木桶理论短板决定容量。消去法移动短板那一侧的指针相当于排除了该短板与其他所有远端边组合的可能性因为它们一定比当前面积小。