The best time to climb a ladder & sell shares (notes of the runner)

Climbing a ladder

70. climb stairs - Power button （LeetCode）

At first I was going to use recursion to solve the problem , Because this is actually a Fibonacci sequence .

The code is as follows

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

But I can't

Scrolling array

So we can use the current rolling array to solve the problem

The code is as follows :

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

---

The best time to buy and sell stocks

The best time to buy and sell stocks - Power button （LeetCode）

The title means to give you an array , You can only subtract the previous array value from the latter value , Return the maximum value .

Violence law

The direct use time complexity is O(n²) The method code of is as follows . But timeout .

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

Just go through

We will first minprices Assign a value to 10⁵ because prices[i] The maximum value of 10⁴

class Solution {
    
public:
    int maxProfit(vector<int>& prices) 
    {
    
        int minprices = 1e5;// The maximum value is 1*10^5^
        int ret = 0;
        for(int i =0;i<prices.size();i++)
        {
    
            minprices = min(minprices,prices[i]);// Record the minimum value of each node 
            ret = max(ret,prices[i]-minprices);// Used to record the maximum value of each node minus the previous lowest value .
        }
        return ret;
    }
};

We only need to traverse this node once, because every time we walk through a node, we will judge whether it is smaller than the previous value , If you are young, write it down .

In this way, we can directly subtract the previous minimum value from the current position when subtracting, and we earn the most in this case .

Then compare with the maximum value we can earn recorded before, and we can get the maximum value we want through a traverse .