狗家店面挂经，求大米

没在leetcode上见过这题，只给出了个brute force O(N^2)解，被告知有O(NlogN)和O(N)解。sigh，求大米求安慰。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. int getMaxValue(vector<int>& nums) {
   
2.     int n = nums.size();
   
3.     if (n < 2) {
   
4.         return -1;
   
5.     }
   
6. 
   
7.     int pre = 0;
   
8.     int result = nums[1]+1+nums[0];
   
9.     for (int i=1; i<n; ++i) {
   
10.         result = max(result, nums[i]+i+nums[pre]-pre);
    
11.         if (nums[pre] - pre < nums[i] - i) {
    
12.             pre = i;
    
13.         }
    
14.     }
    
15. 
    
16.     return result;
    
17. }

复制代码

这个应该是李寇要死舅舅

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主发现p[i]不知道为啥显示成了p，所以上面p是p[i].

留名～^_^

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问 这道题 和蠡口 11 像么？ 双指针 可以做么？
f = p[i].val + p[j].val + |p[i].x - p[j].x|
指针i从头开始 j从末尾 初始 让 max = MAX_MIN， 然后从两边开始扫 每次增加或者减少i或者j 取决于p[i] 和p[j]哪个较小。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

djmiss 发表于 2021-6-2 09:03
题目没说按x排序啊，排序后O(n)很简单，不排序怎么O(n)?

不排序不可能O[N]