“This is the 29th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Today’s topic is simple, very typical through the maintenance of variables to optimize the complexity of the topic, see this problem for the first time to enumerate violence no problem, but after should think of optimization method

A daily topic

Today’s question of the day 2016. The maximum difference between incremental elements. The difficulty is simple

  • Nums [j] -nums [I] = 0 <= I < j < n and nums[I] < nums[j]

  • Returns the maximum difference. If no I and j satisfy the requirement, return -1.

 

Example 1:

Enter: nums = [7.1.5.4] output:4Explanation: The maximum difference occurs at I =1And j =2When, nums[j] -nums [I] =5 - 1 = 4. Notice, although I is equal to1And j =0When, nums[j] -nums [I] =7 - 1 = 6 > 4, but I > j does not meet the requirements of the problem, so6Not a valid answer.Copy the code

Example 2:

Enter: nums = [9.4.3.2] Output: -1Explanation: There is no combination of I and j that satisfies both I < j and NUMs [I] < nums[j].Copy the code

Example 3:

Enter: nums = [1.5.2.10] output:9Explanation: The maximum difference occurs at I =0And j =3When, nums[j] -nums [I] =10 - 1 = 9 。
Copy the code

 

Tip:

  • n == nums.length
  • 2 <= n <= 1000
  • 1 <= nums[i] <= 109

Answer key

Double loop violence solution

The simplest way to find two numbers is to double loop through the array, iterate over each combination, and find the one that meets the requirements of the question.

  1. Define array length n maximum difference Max

  2. Double loop through the number set

  3. I < j and nums[I] < nums[j]

  4. If the requirement is met, the difference value is greater than the maximum difference value defined. If the difference value is greater than the maximum difference value defined, the replacement is performed

  5. Max is the answer to the problem

/ * * *@param {number[]} nums
 * @return {number}* /
var maximumDifference = function (nums) {
  let n = nums.length;
  let max = -1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i < j && nums[i] < nums[j]) {
        if(nums[j] - nums[i] > max) { max = nums[j] - nums[i]; }}}}return max;
};
Copy the code

Maintain a minimum – Optimize time complexity to O(n)

For violent solutions, we can also maintain a minimum, because we need nums[j] -nums [I], and j> I, so we can just iterate over the array once, and during the iterate, we can maintain a current minimum, min, which represents the smallest term from 0 to j, So the j that I’m going to iterate over needs to be the maximum difference and I can just subtract the maintenance minimum.

/ * * *@param {number[]} nums
 * @return {number}* /
var maximumDifference = function (nums) {
  const n = nums.length;
  let ans = -1,
    min = nums[0];
  for (let j = 1; j < n; j++) {
    if (nums[j] > min) {
      ans = Math.max(ans, nums[j] - min);
    } else{ min = nums[j]; }}return ans;
};
Copy the code