爬梯子＆＆卖卖股份的最佳时期(跑路人笔记)

爬梯子

70. 爬楼梯 - 力扣（LeetCode）

刚开始我准备使用递归来解决问题,因为这个其实就是一个斐波那契数列.

代码如下

class Solution {
    
public:
    int climbStairs(int n) 
    {
    
        if(n == 1)
            return 1;
        if(n == 2)
        {
    
            return 2;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
};

但是不行

滚动数组

所以我们就可以用现在的滚动数组来解决问题

代码如下:

class Solution {
    
public:
    int climbStairs(int n) 
    {
    
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) 
        {
    
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

---

买卖股票的最佳时机

买卖股票的最佳时机 - 力扣（LeetCode）

题目意思是给你一个数组, 只能用后面的值减去前面的数组值,返回最大值即可.

暴力法

直接使用时间复杂度为O(n²)的方法代码如下.但是超时.

class Solution {
    
public:
    int maxProfit(vector<int>& prices) 
    {
    
        int ret = 0;
        int tmp = 0;
        for(int i = 0;i<prices.size();i++)
        {
    
            for(int j = i+1;j<prices.size();j++)
            {
    
                tmp = prices[j] - prices[i];
                ret = ret>tmp?ret:tmp;
            }
        }
        return ret;
    }
};

只遍历一遍

我们先将minprices赋值给10⁵因为prices[i]的最大值是10⁴

class Solution {
    
public:
    int maxProfit(vector<int>& prices) 
    {
    
        int minprices = 1e5;//最大值为1*10^5^
        int ret = 0;
        for(int i =0;i<prices.size();i++)
        {
    
            minprices = min(minprices,prices[i]);//记录每个节点的最低值
            ret = max(ret,prices[i]-minprices);//用于记录每个节点和前面最低值相减的最大值.
        }
        return ret;
    }
};

我们这个只需要遍历一次因为我们每走过一个节点都会判断他是否比前面的值要小,如果小就记录下来.

这样后面我们在相减的时候就可以直接用当前位置减去前面的最小值而且这样的时候我们赚的是最多的.

再和之前记录的我们能赚的最大值进行比较通过一次遍历我们就可以得到我们想要的最大值了.