LeetCode: address

Topic request

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

Example 2:

Input: hours = [6,6,6] output: 0Copy the code

Tip:

  • 1 <= hours.length <= 104
  • 0 <= hours[i] <= 16
Train of thought

Monotonous stack:

Maintaining a poorly performing period means that the two time points adjacent to the stack are both poorly performing periods. Base point 0 is set to determine the first downhill section; Need to get the prefix and the uphill segment, so maintain a monotone decrement stack; The prefix and need to be traversed from behind.

code
/** * @param {number[]} hours * @return {number} */ var longestWPI = function (hours) { let len = hours.length; let change = new Array(); hours.forEach(val => { change.push(val > 8 ? 1:1); }); let preSum = new Array(); preSum[0] = 0; change.forEach((val, ind) => { preSum.push(val + preSum[ind]); }) let stack = []; stack.push(0); preSum.forEach((val, ind) => { if (preSum[stack[stack.length - 1]] > val) { stack.push(ind); } }) let result = 0; for (let i = len; i >= 0; i--) { while (stack.length > 0 && preSum[i] > preSum[stack[stack.length - 1]]) { result = Math.max(result, i - stack.pop()); } } return result; };Copy the code