-
Notifications
You must be signed in to change notification settings - Fork 84
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
盛最多水的容器 #5
Comments
Open
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
题目
分析
经典的木桶问题,能盛水的多少取决于短边的高度。
解答
方法1、
暴力破解,使用时间复杂度为O(n^2)的算法
解法2、
从数组两边向中间靠拢,记录每一次计算的面积,当左边小于右边时,使左边向右移动,因为此时右边不管怎么动,左边已经决定了面积的大小,除非右边移动后比左边还要小,但这是获取的面积只会更小。反之亦然。只需一遍遍历即可,时间复杂度为O(n)
The text was updated successfully, but these errors were encountered: