当前位置:网站首页>笔试面试题目:盛水最多的容器
笔试面试题目:盛水最多的容器
2020-11-08 10:30:00 【osc_1ajf1srl】
原文发表于:
今天周末,来看G公司的一道面试题:
求max{|i-j|*min{a[i], a[j]}}的值,其中a是正整数数组,i和j的区间为[0, n-1].
这其实就是leetcode中的“盛水最多的容器”,如下:
鲁迅说:暴力可以解决一切问题。
胡适说:暴力能解决的问题,都不是问题。
因为i和j的可能性是有限组合,所以暴力算法能得到结果,但无法通过面试。
用动态规划吗?貌似也不好动态规划。
我们可以采用双指针,分别指向头尾,计算出盛水值。然后向中间搜索,尝试找出更大的盛水可能性。
木桶理论告诉我们:对于两块确定的盛水挡板而言,盛水的多少是由短板决定的。
所以,在向中间搜索时,从短板侧向中间移动指针,才有可能产生更大的盛水值。
这是一个核心结论。
至于代码,很简单,来看下:
func maxArea(a []int) int {
n := len(a)
if n < 2 {
return 0
}
if n == 2 {
return min(a[1], a[0])
}
max := min(a[n - 1], a[0]) * (n - 1)
i := 0
j := n - 1
for i < j {
if a[i] < a[j] {
i++
}else {
j--
}
area := min(a[i], a[j]) * (j - i)
if area > max {
max = area
}
}
return max
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
结果:
该算法能正常通过面试,祝大家获得自己心仪的offer.
周末愉快。
版权声明
本文为[osc_1ajf1srl]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4272693/blog/4707996
边栏推荐
- python学习 day1——基础学习
- Basic concepts of computer network (5) basic principles of local area network
- Flink's sink: a preliminary study
- 攻防世界之web新手题
- 成功解决An error ocurred while starting the kernel
- PX4添加新的应用
- Python loop distinction (while loop and for loop)
- Recommend an economic science video, very valuable!
- More than 50 object detection datasets from different industries
- AMD Zen3首发评测:频率超5GHz,IPC提升不止19%,这次真的Yes了 - 知乎
猜你喜欢
随机推荐
ulab 1.0.0发布
Web novice problem of attacking and defending the world
Close to the double 11, he made up for two months and successfully took the offer from a large factory and transferred to Alibaba
Cloud Alibabab笔记问世,全网详解仅此一份手慢无
Python loop distinction (while loop and for loop)
M 端软件产品设计思虑札记 - 知乎
AMD Zen3首发评测:频率超5GHz,IPC提升不止19%,这次真的Yes了 - 知乎
Flink的sink实战之一:初探
211考研失败后,熬夜了两个月拿下字节offer!【面经分享】
The difference between vivoy 73s and glory 30 Youth Edition
阅读心得:FGAGT: Flow-Guided Adaptive Graph Tracking
盘点那些你没想到的云计算应用场景(上)
双向LSTM在时间序列异常值检测的应用
Deeplight Technology Bluetooth protocol SRRC certification services
C++在C的基础上改进了哪些细节
[summary series] technical system of Internet server: high performance database index
解决Safari浏览器下载文件文件名称乱码的问题
FORTRAN77从文件中读入若干数据并用heron迭代公式开方
SQL Server 2008R2 18456错误解决方案
狗狗也能操作无人机!你没看错,不过这其实是架自动驾驶无人机 - 知乎