“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”
[B] [C] [D]
Hours, which records the number of hours an employee works every day.
We consider a “tired day” when employees work more than eight hours a day.
The so-called “good performance period” means that during this period, the “tired days” is strictly greater than the “not tired days.”
Return the maximum length of a good time period.
Example 1:
Input: hours = [9,9,6,0,6,6,9] output: 3 explanation: the longest period of good performance is [9,9,6].Copy the codeTip:
1 <= hours.length <= 100000 <= hours[i] <= 16
The period of good performance is defined as the period in which the number of tired days is greater than the number of non-tired days
- Gets all subintervals of the given schedule
- Determine whether this is a period of good performance
- Get the maximum of all good performance periods
But that’s inefficient, so what’s a better solution to this problem?
Because each day has only two possibilities, either a tired day or an untired day, and because we should get more tired days than untired days
So first we can convert the elements of hours to 1 and -1 depending on whether they are >8. Using Example 1, the result is shown below:
So what are we doing here, just to get ready for prefixes and arrays
The prefix sum here is that each term is equal to the sum of all the previous terms
The result after the prefix and sum of the above results is as follows:
The first digit of the prefix sum is initialized to 0 for subsequent operations, so the i-th value of the prefix sum corresponds to the i-th +1 value of the prefix and array
Once we have the prefix and array, we subtract the previous term from the latter, and the resulting value is the sum of the number of days worked in the interval
For example: prefixes and arrays
Subscript 2 minus subscript 0 is 2, indicating that the number of tired days is 2 more than the number of untired days in the previous two days
The result of subtracting subscript 1 from subscript 4 is -1, indicating that the number of tired days from the second day to the fourth day is one less than the number of non-tired days
The best representation for this position is the value in the prefix sum minus the minimum value in front of it.
The conditions for a good performance period are shown below:
So how do we quickly get the minimum in front of that position, and here we’re going to use another trick: decrement stack
Monodecrement stack in JS is an array in strict descending order, then inserting and fetching values from the end of the array each time
The monotone decrement stack we need to maintain here is the minimum in prefixes and arrays
So the monotone decrement stack from the prefix and array above is shown below:
We then initialize the resulting value res = 0
The prefix and array are then iterated backwards and forwards
If the value is greater than the value at the top of the monotone decrement stack, the top of the stack pops up
The duration is the current subscript minus the top stack subscript, and an attempt is made to update the resulting value
Continue until the value is no greater than the top of the stack
When the subscript is equal to the value of the result, there is no need to iterate and exit the loop
Because when the lower index value is less than or equal to the result value, the best result obtained in this interval will not be greater than the result value, so you can exit the loop
Finally, we have the maximum period of good performance
The overall process is as follows:
The code is as follows:
Var longestWPI = function(hours) {const preSum = [0], len = hours.length; For (let I = 0; i<len; i++){ preSum[i+1] = preSum[i]+(hours[i]>8? } // Const stack = [0]; for(let i = 1; i<=len; I ++){if(preSum[I]<preSum[stack[stack.length-1]]) stack.push(I)} for(let i = len; i>res; i--){ while(preSum[i]>preSum[stack[stack.length-1]]){ res = Math.max(res,i-stack.pop()) } } return res; };Copy the codeAt this point we have completed Leetcode-1124 – the maximum period of good behavior
If you have any questions or suggestions, please leave a comment!