“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 code

Tip:

  • 1 <= hours.length <= 10000
  • 0 <= 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

  1. Gets all subintervals of the given schedule
  2. Determine whether this is a period of good performance
  3. 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 code

At this point we have completed Leetcode-1124 – the maximum period of good behavior

If you have any questions or suggestions, please leave a comment!