门户网站建设投入,郓城做网站公司,做网站工资高不高,怎样用dw做网站导航条欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家#xff01;
链接#xff1a;
11-盛最多水的容器
直觉
这个问题可以通过可视化图表来理解和解决。 通过图形化这个…欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家
链接
11-盛最多水的容器
直觉
这个问题可以通过可视化图表来理解和解决。 通过图形化这个问题可以简化解决过程。我们可以使用双指针技术来解决它。起初左指针设置在数组的起点右指针设置在数组的终点。目标是找到最大的可能面积这个面积受指针指向的较短高度的限制。面积可以通过公式 min(height[left], height[right]) * (right - left) 计算。容器的高度受较短的两个高度之一限制。
为了最大化面积我们应该移动指向较短高度的指针。这是因为移动指向较高高度的指针不会有助于找到更大的面积因为容器的高度仍然会受较短高度的限制。具体来说新高度将是 min(height[left], height[new_right])它将小于或等于之前的较短高度并且间隔距离也会缩小。因此如果左指针指向较短高度我们将其向右移动。相反如果右指针指向较短高度我们将其向左移动。
方法
初始化两个指针左指针在数组起点右指针在数组终点。初始化一个变量 res 来存储最大面积。使用公式 res max(res, min(height[left], height[right]) * (right - left)) 来计算面积并更新 res。移动指向较短高度的指针以尝试找到更大的面积。设置提前停止条件设 h 为数组中的最大高度。如果 (right - left) * h 小于 res则意味着不可能找到更大的面积因此我们可以跳出循环。
复杂度
时间复杂度 O ( n ) O(n) O(n) 我们只用两个指针遍历数组一次时间复杂度为线性。 空间复杂度 O ( 1 ) O(1) O(1) 无论输入大小如何我们只使用了常量空间。
代码
class Solution(object):def maxArea(self, height)::type height: List[int]:rtype: intl 0r len(height) -1h max(height)res 0while l r:if (r-l) * h res:breakres max(res, min(height[l],height[r]) * (r-l))if height[l] height[r]:l1elif height[l] height[r]:r-1return res
