[TOC]

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

2104. Sum of subarray ranges

For a long time did not brush the question for me, suddenly began to brush the question, nothing else, has been used to participate in the activities of digging gold, but also can promote their own review of the algorithm, after all, not practice for a long time, really rusty

This month began to brush questions, try to write questions, I hope to help you

I. Title Description:

Give you an integer array nums. In NUMS, the range of a subarray is the difference between the largest and smallest element in the subarray.

Returns the sum of all subarray ranges in NUMS.

A subarray is a contiguous non-empty sequence of elements in an array

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

Looking at the description and examples of this problem, we should get the following information

  • To find all the subarrays in the given array, the order of the elements in the subarrays must be the same as the order of the elements in the original array
  • For each subarray, we need to find the maximum and minimum in that subarray, and calculate the difference
  • We need to sum up the results of all the subarrays

The thing to notice about this subarray is, if it’s contiguous, it’s not empty

If we think that we can make subarrays like this then we’re thinking in the wrong direction, and we have to be careful here

So given what we know, we can do it step by step, so how do we find subarrays

Since we need to find the difference between the largest and smallest number in the subarray, we will directly ignore the case that there is only one element in the subarray. First, according to the meaning of the question, the subarray must be non-empty, so if the subarray has only one element, the difference between the largest and smallest number is 0

We can use Example 3 above to illustrate:

Minus 4, minus 2, minus 3,4, 1Copy the code

According to the diagram above, it’s not hard to understand,

  • You specify the first element on the left as the starting position, and then keep expanding to the right, calculating the difference between the maximum and minimum values of each subarray, until you reach the length of the array
  • And then the second element from the left, and then we expand to the right
  • Finally, the search is complete when the starting element refers to the rightmost element of the array
  • And finally sum the differences of all the subarrays

2. Try coding

So, based on the above diagram and logic, it’s not hard to write code that looks like this

However, for a larger number of use cases, the actual situation is 56 use cases, but for use cases with more complex data, the time limit will be exceeded

A closer look at our code shows that we actually use a three-tier for loop, which is definitely not allowed in a production environment

Therefore, there must be room for improvement

3. Think and explore

Above to calculate maximum and minimum value of an array of each child is the same, screening of subarray way is the same, so, whether we can change an idea to take a look at this problem, try to screen out subarray Max, and min respectively corresponding to the place, in the end, the direct calculation of the corresponding data difference, sum again can, This eliminates three for loops

For example, in the figure above, we can calculate the maximum and minimum values of [4,-2] in the first step, then we only need to compare and calculate the results of [4,-2] in the subarray of [4,-2]

For example, when calculating the maximum value of [4,-2,-3], you only need to compare the maximum value of the subarray [4,-2,-3] with -3, so it must be the maximum value of [4,-2,-3]

The same is true for the minimum value, and the same is true for all subarrays

Conclusion:

If you have more to think about, analyze and summarize, add them all

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~