很多时候,题目描述反而会成为你理解题目本质的阻隔。比如,下面这题:
Q122: 买卖股票的最佳时机 II
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
看似是需要进行买卖操作,并且买的时间点总是要在卖的前面。但如果你用这个思路来做题,就会走到坑里去。当你对题目本质的理解有偏误时,你就不可能写出正确的代码。
我最开始想要用两个指针来分别记录位置,找到极大值和极小值,然后用数组保存。但是后来发现这样做漏洞极多。逻辑非常复杂,几乎不可能涵盖所有的情况。计算机的思想应该是简化、可推广,而不是让单个逻辑变得极复杂。
于是我重看了男票写的代码。然后发现自己对题目的理解并不透彻。看似这道题是要你找到买点和卖点,但实质上是要求最大的收益。而最大的收益实际上等于所有price[i]-price[i-1],when price[i]>price[i-1]。这个逻辑只比较相邻的两个数,看似粗糙,但它确实可以通过所有用例的检查。
public int maxProfit(int[] prices) {
// 买入和卖出根本无所谓
// 只要是递增的,加上就好
if(prices.length == 0) return 0;
int res = 0;
for( int i=0;i<prices.length;i++){
if(i == 0) continue;
if(prices[i]>prices[i-1]){
res += (prices[i]-prices[i-1]);
}
}
return res;
}
比如:
[1] prices[] = {1,3,5,6,8}。那么result = 3-1+5-3+6-5+8-6 = 8-1 = 7;
[2] prices[] = {6,8,4,9,1,3}。那么result = 8-6+9-4+3-1 = 2+5+1 = 8;
总之,这个方法能行得通,归根结底是如同方程式[1],如果是单调递增,则最大-最小=最大-第二大+第二大-第三大....
因此,这可能就叫做简洁才是美吧。