Topic link

Leetcode-cn.com/problems/lo…

Title introduction

Hours, which records the number of hours an employee works every day. We consider an employee to be working more than 8 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

The sample

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

Their thinking

Use prefix + monotonic stack. 1. Prefix: Presum = [0,1,2,1,0, -1, -2, -1]; presum = [0,1,2,1,0]; It’s the longest segment that has a score of 1 greater than negative 1. 4. Maintain a stack where the index of the elements in presum is strictly monotonically decrement, e.g., 0, -1, -2. So stack= [0, 5, 6]; 5. Traverses the presum array from back to front, comparing it with the index pointing to the element at the top of the stack. If the subtraction is greater than 0, it continues off the stack until it is less than 0, and then updates the current maximum width

Code implementation

/ * * *@param {number[]} hours
 * @return {number}* /
 var longestWPI = function(hours) {
         // Record the length of hours
         const n = hours.length;
         // Create source array with the same length as hours
         const source = new Array(n).fill(0);
         // Record the current score in the source array
         for(let i=0; i<n; i++){if(hours[i] > 8) {
                 source[i] = 1;
             }
             else {
                 source[i] = -1; }}// Create the presum array.
         const presum = new Array(n + 1).fill(0);
             // Compute the prefix sum
         for (let i = 1; i < n + 1; i++){
          presum[i] = presum[i - 1] + source[i - 1];
        }
        // Define the length
        let max = 0;
        const stack = [];
            // Add a decrement element index to the stack
        for (let i = 0; i < n + 1; i++){
          if(! stack.length || presum[stack[stack.length-1]] > presum[i]) { stack.push(i); }}let i = n;
        while (i > ans) {
          while (stack.length && presum[stack[stack.length-1]] < presum[i]) {
            ans = Math.max(ans, i - stack.pop());
          }
          i -= 1
        }
        return ans;
 }
Copy the code