Manacher算法，O(n)。思路写在注释里了。可能有有同学好奇为啥是O(N)的。太麻烦没自己证明，不过可以粗略体会下：for循环毫无疑问是O(n)的，问题在于“统计未知部分”这里的while循环不好估计。已知是统计未知部分时起始位置由，得，则，而更新时i-ans[i]<=best-ans[best]  class Solution { public: /* Manacher算法 */ int getLongestPalindrome(string A, int n) { //加间隔符统一奇数、偶数长度的回文串，方便处理 // 例子：cbc --> #c#b#c# n=A.siz...

时间复杂度O(nlogn) 我觉得大家的方案都有点太麻烦了……观察目标函数：区间中的最小数*区间所有数的和第一反应就是按照值从小到大处理点，这样的话区间中的最小数*就已知了，我们只用考虑区间就行。 那么，区间有多大呢？其实题目中又一个很强的约束  区间内的所有数字都在[0, 100]的范围内;  因此区间自然是越大越好，具体来说，向左延伸到比他小的数字，向右延伸到比它小的数字。换个角度来说：我们插入的点把区间切成两半了，每次处理新的点时，我们只需要获取它当前的区间就行。 那么如何获取区间呢？显然的，右端点：最小的比它大的切分点,左端点：最大的比它小的切分点平衡二叉树的经典使用场景。 时间复杂度...

同志们想复杂了，用的方法既满又难写，实际上解法还是很简单的。注意这道题有一个限制：数字都在[0, 100]的范围内，这其实可以拆解为两点：1.值非负，这决定了我们的算法2.值小与100，这省了我们很多事，对笔试非常友好。 注意看目标函数：区间中的最小数 * 区间所有数一个非常自然的想法是我们从小到大遍历数值，这样“区间的最小数”就确定了。然后我们考虑区间有多大，显然，由于值非负，区间等于：[向左直到遇到已经插入的点,向右直到遇到已经插入的点]由于我们是从小到大添加的数，那么实际上就是找：最大的比他坐标小的分割点，最小的比它坐标大的分割点，这是典型的平衡二叉树。时间复杂带但是，平衡二叉树对于py...

有同学用优先级队列/最大堆做，其实不用那么麻烦。将点按照x坐标从大到小排序并遍历，那么实际上就可以无视X坐标，只关心Y坐标就行。换句话说：只需要知道之前遍历的点的最大Y值是多少即可 n=int(input()) points=[ [int(x) for x in input().split()] for i in range(n)] points.sort(key=lambda x:-x[0]) ans=[] top=points[0][1] for p in points: if top>p[1]: continue top=p[1] ans.append(p) #ans.sort(k...

我亲爱的小同学们，这其实是个脑筋急转弯…… - -|||一个位置的液柱高度只取决于三个因素：左边最高多高、右边最高多高、底多高。所以，O(n)扫描记录一下前两个参数，然后直接算就行……  int n=arr.size(); auto lm=new int[n+10];lm+=1; auto rm=new int[n+10];rm+=1; lm[-1]=rm[n]=0; for (int i=0;i<n;++i) { lm[i]=max(lm[i-1],arr[i]); rm[n-i-1]=max(rm[n-i],arr[n-i-1]); } long long res=0; for (i...

O(n),其他解法未免也太啰嗦了。  j=M-1; for (int i=0;i<n;++i) { while (j>0 && val[i][j]>K) --j; if (val[i][j]==K) {cout<<"Yes"<<endl;return 0;} } cout<<"No"<<endl;return 0;  关键点在于不等关系是有传递关系的。 如果一个位置(i,j)的数>K，显然它下边、右边、右下的数一定>K，因此在后边的查询中看都不用看。 当我们按照上往下(i增加)的顺序遍历行时,发现最右...