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.
Their thinking
You can change the number of working hours to tired days +1 and untired days -1
The sum of all working time intervals is then calculated using the prefix sum
For example: [6, 9, 9, 0, 6, 6, 9] into: [1, 1, 1, 1, 1, 1, 1] prefix and: [0, 1, 2, 1, 0, 1, 2, 1]
So we’re looking for the maximum length of the well-behaved period, and the summation gives us the sum of the intervals which means that the sum of the intervals greater than 0 is the well-behaved period.
code
Var longestWPI = function(hours) {let preSum = new Array(hours.length + 1).fill(0); for (let i = 0; i < hours.length; i++) { if (hours[i] > 8) preSum[i + 1] = preSum[i] + 1; Else preSum[I + 1] = preSum[I] -1} let stack = [0]; for (let i = 0; i < preSum.length; I ++) {if (preSum[I] < preSum[stack[stack.length-1]]) stack.push(I)} console.log(stack) console.log(preSum let max = 0 // 0, 1, 2, 1, 0, -1, -2, -1 for (let i = preSum.length - 1; i > max; i--) { while (stack.length && preSum[stack[stack.length-1]] < preSum[i]) { max = Math.max(max, i - stack.pop()) } } return max };Copy the code