[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 ~