赞
踩
来源:投稿 作者:LSC
编辑:学姐
有一个无序的整数数组,从数组中可以任意选择两个不重复的数字,以这两个数字所在的位置,可以建立两堵墙,以两个数字坐在位置的距离为底,可以生成一个容器,这个容器的可以装 min(nums[i], nums[j])*[j-i] 单位水,请问最大的装水单位是多少?
方法1: 暴力
- int n;
- int a[10005];
- int volume()
- {
- int res = 0;
- int l = 0, r = n - 1;
- for (int i = 0; i < n; ++i)
- {
- for (int j = i + 1; j < n; ++j)
- {
- int mi = min(a[i], a[j]);
- res = max(res, mi * (j - i));
- }
- }
- return res;
- }

方法2: 双指针
- int volumn()
- {
- int res = 0;
- int l = 0, r = n - 1;
- while(l < r)
- {
- int mi;
- if (a[l] >= a[r])
- {
- mi = a[r];
- res = max(res, mi * (r - l));
- r--;
- }
- else
- {
- mi = a[l];
- res = max(res, mi * (r - l));
- l++;
- }
- }
- return res;
- }

面试官非常友好,看起来很成熟温和,我答的不太好的问题,也没为难我,很愉快很感激!
关注下方《学姐带你玩AI》
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。