leetCode 121. Best Time to Buy and Sell Stock 数组

  1. 云栖社区>
  2. 博客>
  3. 正文

leetCode 121. Best Time to Buy and Sell Stock 数组

科技小能手 2017-11-13 22:33:00 浏览495
展开阅读全文

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)


Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

题目大意:

在一个数组中,用后面的元素减去前面的元素得到最大值,返回这个最大值。

思路:

可以使用双循环来出来,但是效率太低。没有通过。

采用记录当前之前的最小值,用当前值减去之前最小的值获得一个临时最大值,遍历整个数组,找到最大值。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1)
            return 0;
        int max = 0;
        int curMin = prices[0];
         
        for(int i = 1;i<prices.size();i++)
        {
            if(prices[i] - curMin > max)
                max = prices[i] - curMin;
            if(prices[i] < curMin)
                curMin = prices[i];
        }
        return max;
    }
};



本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1837145

网友评论

登录后评论
0/500
评论
科技小能手
+ 关注