题目描述
本题主要采用了双指针算法,其实本质上有贪心的思想在其中.
以下是我对本题鄙夷的见解:
通过比较左右指针所代表的值,来确定指针的移动.
如果某一指针的值小于另一指针的值(这里都指的是指针所指向的值而不是地址,本身指针也是伪指针)
说明该指针不在适合做边界了,下一次就需要移动它.
原因:如果移动另一指针,他们之间的距离一定会变短,下一次计算面积时只有两种选择,但无论哪种选择矩形的一条边一定<=之前的边.故面积一定会小于上一个值,也就是说这种计算是完全可以避免的,所以只有当移动较短一个指针时才有可能大于上一个面积值.这样才有意义.
算法1
(双指针) $O(n)$
时间复杂度
$O(n)$
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for (int i=0;i<n;++i) scanf("%d",&a[i]);
int ans=-1000;
int l=0,r=n-1;
while (l<r)
{
int s=min(a[l],a[r])*(r-l);
ans=max(ans,s);
if (a[r]>=a[l]) l++;
else r--;
}
printf("%d",ans);
return 0;
}