LeetCode 2016. Maximum difference between incremental elements

2016. The maximum difference between incremental elements Answer key

Title source ：2016. The maximum difference between incremental elements

2022.02.26 A daily topic

Daily question column address ：LeetCode The solution of one question every day is being updated ️

Today's topic is relatively simple , seek nums[j] - nums[i] The maximum difference between the two , And also need to meet nums[j] > nums[i] And j > i

Law 1 ： Violent simulation

The first method is to simulate directly , Find the minimum

class Solution { 
    
public: 
    int maximumDifference(vector<int>& nums) { 
    
    int len = nums.size();
    int res = -1;
    for (int i = 0; i < len; i++)
        for (int j = i + 1; j < len; j++)
            if (nums[j] > nums[i]) res = max(res, (nums[j] - nums[i]));
    return res;
    }
}

class Solution { 
    
    public int maximumDifference(int[] nums) { 
    
        int len = nums.length;
        int res = -1;
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j < len; j++)
                if (nums[j] > nums[i]) res = Math.max(res, (nums[j] - nums[i]));
        return res;
    }
}

• Time complexity $O(n^2)$
• Spatial complexity $O(1)$

Law two ： Optimize

We need to find

n

u

m

[

j

]

−

n

u

m

[

i

]

num[j]-num[i]

num[j]−num[i] The maximum value of the difference , At the same time, we should satisfy

n

u

m

s

[

j

]

>

n

u

m

s

[

i

]

nums[j] > nums[i]

nums[j]>nums[i]

Then we can just traverse

j

j

j, then Mark

[

0

,

j

−

1

]

[0,j-1]

[0,j−1] Minimum of , And

n

u

m

[

j

]

num[j]

num[j] Make mistakes , Get the final result

class Solution { 
    
public:
    int maximumDifference(vector<int> &nums) { 
    
        //  Define the result variable , The initial value is assigned to  -1
        //  If there are no number pairs that meet the conditions, it will directly return  -1
        int res = -1;
        //  Make  i  stay  [0,j)  Within the scope of  
        int i = nums[0];
        //  Make  j  Traverse  nums 
        for (int j = 1; j < nums.size(); j++)
            //  If meet  nums[j] > nums[i]
            //  Just do bad and  res  Compare and take the maximum value 
            if (nums[j] > i)
                res = max(res, (nums[j] - i));
            else
                //  If not satisfied  nums[j] > nums[i]
                //  Just update  i  Value 
                i = nums[j];
        
        return res;
    }
};

class Solution { 
    
    public int maximumDifference(int[] nums) { 
    
        //  Define the result variable , The initial value is assigned to  -1
        //  If there are no number pairs that meet the conditions, it will directly return  -1
        int res = -1;
        //  Make  i  stay  [0,j)  Within the scope of  
        int i = nums[0];
        //  Make  j  Traverse  nums 
        for (int j = 1; j < nums.length; j++)
            //  If meet  nums[j] > nums[i]
            //  Just do bad and  res  Compare and take the maximum value 
            if (nums[j] > i) res = Math.max(res, (nums[j] - i));
            else
                //  If not satisfied  nums[j] > nums[i]
                //  Just update  i  Value 
                i = nums[j];

        return res;
    }
}

• Time complexity $O(n)$
• Spatial complexity $O(1)$