今天遇到了一个十分牛逼的算法 先把代码贴上来 题目在leetcode里
int maxProfit(int* prices, int pricesSize){ int i = 0; int valley = prices[0]; int peak = prices[0]; int sum = 0; while(i < pricesSize-1){ while(i<pricesSize-1 && prices[i] >= prices[i+1]){ i++; } valley = prices[i]; while(i<pricesSize-1 && prices[i] <= prices[i+1]){ i++; } peak = prices[i]; sum += peak-valley; } return sum; }我认为这个算法的牛逼之处在于找峰和找谷的操作 while(i<pricesSize-1 && prices[i] >= prices[i+1]){ i++; } 这个while循环,在本元素大于后一个元素的时候,i就往后移动,当移动不了时,说明这就是个谷(比之前的都小,比后面的也都小)了,直接赋值valley = prices[i]; 同理,找峰的操作也是一样 还有注意一个细节,这个算法里面只用了一个i,这保证了峰的下标一定比谷的下标大(因为我们做的是股票题,卖股的日期一定要大于买的日期)
