爬梯子

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;
    }
};