目录
Leetcode 121
题目与分析
题目大意是有一个股票价格序列，找到最优的买进卖出时间点，算出最高差价。O(N)时间可以找到最低买入点和最大差价。
虽然是很简单的一道题，但这个解题的范式是非常典型的。
基本范式：
res = A[j] - A[i], i < j
find Max(res)
如果没有i<j的限制，那就是一次遍历找到最大最小值做差值就可以了。
有了下标的限制之后，下标限制中小的那一项照旧更新，另一项的更新改为直接更新目标式。即，最小值的更新如旧，最大值的更新改为最大查值的更新。
.
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty())
return 0;
int res = 0, buy = prices[0];
for(int i = 0; i < prices.size(); i++){
res = max(res, prices[i] - buy); // 目标式的更新
buy = min(buy, prices[i]); // 第二项的更新
}
return res;
}
};
.
Leetcode 1014
题目与分析
题目大意是，挑选最优的景点组合，组合的评分标准是两个景点的分数相加，再减去两景点间的距离。
说得这么复杂，其实跟上面一道题本质是一样的。
归纳到基本范式：
res = (A[j] - j) + (A[i] + i), i < j
find Max(res)
区别在于，中间是+连接，那么代码中的第二项本来用min更新，这里就改用max做更新。
.
代码
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& A) {
int res = 0, max_i = A[0]; // A[0] + 0;
for(int j = 1; j < A.size(); j++){
res = max(res, max_i + A[j] - j); // 目标式的更新
max_i = max(max_i, A[j] + j); // 第二项的更新
}
return res;
}
};
.
Leetcode 1131
题目与分析
这是Leetcode146周赛的第四题，当时看到觉得很眼熟，但没来记得做（啊，我好菜orz
后来看评论区大神的代码，觉得大神代码虽然写得很好，但那个解释就很奇怪。后来想起来，跟前面两道题其实是同类题。
但要把这道题归纳到Leetcode121的基本范式有2个问题：
- 没有i<j的限制，题目只说了 0≤i,j<arr1.length，没有定义i,j之间的关系
- 绝对值怎么处理
如果先无视这两个问题，无脑归纳一下，归纳到基本范式：
res = (A1[j] + A2[j] + j) - (A1[i] + A2[i] + i), i < j
find Max(res)
看上去是不是就很简单了！
我们再来解决上面提到的那两个问题：
-
i<j的限制
如果设f(i,j)=∣arr1[i]−arr1[j]∣+∣arr2[i]−arr2[j]∣+∣i−j∣，由题意不难得知f(i,j)=f(j,i)，所以不妨人为规定 i<j，这样不仅解决了i,j大小关系的限制，同时去掉了第三个绝对值。现在目标式变成：
∣arr1[i]−arr1[j]∣+∣arr2[i]−arr2[j]∣+j−i -
绝对值的处理
回忆刚开始学习绝对值时，老师是怎么教的：如果绝对值符号内的数值大于0，去掉绝对值，内容不变；如果绝对值符号内的数值小于0，去掉绝对值，在式子前面添加负号。
1个绝对值是2种情况，2个绝对值就是4种情况：正正、正负、负正、负负。
没错就是这么简单！不用费心去判断每组i,j到底是4种情况的哪种，只要遍历4遍就可以了。
改进后的基本范式：
p,q = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
res = (p*(A1[j] + A2[j]) + j) - (q*(A1[i] + A2[i]) + i), i < j
find Max(res)
再解释一下，为什么可以无脑拆绝对值：因为最终求的是最大值，如果绝对值拆错了，比如去掉绝对值应该取负的没有取，去掉绝对值不需要取负的取负了，只会导致计算的结果变小，所以在对目标式取max的时候，是不会取到错误的计算结果的。
.
代码
class Solution {
public:
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
int res = 0;
for (int p : {1, -1}) {
for (int q : {1, -1}) {
int min_j = p * arr1[0] + q * arr2[0] + 0;
for (int i = 0; i < arr1.size(); i++) {
int tmp = p * arr1[i] + q * arr2[i] + i;
res = max(res, tmp - min_j); // 目标式的更新
min_j = min(tmp, min_j); // 第二项的更新
}
}
}
return res;
}
};
.
总结
这类范式的3个特点：
- 目标式可以拆成两部分：f(i,j)=f1(i)+f2(j)；
- 有下标限制：i<j；
- O(N)更新下标限制中小的那一项——f1(i) 和目标式f(i,j)
.
其他
Leetcode121 一个更优雅的写法：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0, buy = INT_MAX;
for (int price : prices) {
buy = min(buy, price);
res = max(res, price - buy);
}
return res;
}
};
Leetcode1014 一个加速技巧：
class Solution {
public:
Solution(){
std::ios::sync_with_stdio(0);
cin.tie(0);
}
int maxScoreSightseeingPair(vector<int>& A) {
int res = 0, max_i = A[0]; // A[0] + 0;
for(int j = 1; j < A.size(); j++){
res = max(res, max_i + A[j] - j);
max_i = max(max_i, A[j] + j);
}
return res;
}
};