1124.longest well performing interval

Description

1124. Longest Well-Performing Interval (Medium)

We are given hours, a list of the number of hours worked per day for a given employee. A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8. A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days. Return the length of the longest well-performing interval. Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Example 2:

Input: hours = [6,6,6]
Output: 0

Constraints:

• 1 <= hours.length <= 10⁴
• 0 <= hours[i] <= 16

Solution

Monotone stack

First, we set element greater than 8 to be 1, elements less than 8 to be -1. And we compute the prefix sum of the new array to get a prefix sum array prefix.

We need to find the maximum j - i that satisfies prefix[j] - prefix[i]. First, consider the left endpoint. If prefix[i1] < prefix[i2] and i1 <= i2, then we don't need to consider taking i2 as the left endpoint. So we can traverse prefix forward, and push idx to the stack if prefix[idx] < prefix[stk.top()];

Then, let's traverse prefix backwards. If prefix[j1] > prefix[stk.top()], update res = std::max(res, r - stk.top()), then pop the element in the top. If traverse prefix forward, we may omit res in the case that prefix[j] < prefix[stk.top()].

Hash table

• if (prefix[i] > 0), the i days is well-performing interval, res = max(res, i);
• if (prefix[i] <= 0), if key prefix[i] don't occured in hash table ump before, ump[prefix[i]] = i, otherwise we don't update ump[prefix[i]], since the corresponding value of the key in hash table is less, so the difference (the same as length of interval) is greater; Otherwise the maximum length of well-performing interval ended on the ith day is ump[prefix[i]] - ump[prefix[i] - 1](there must be key prefix[i] - 1 in hash table, or length is 0, which means there is not such interval), since there only are 1 and -1 in new array, the value prefix[i] - 1 must occur earlier than prefix[i] - 2 in array prefix.

Code

Monotone stack

class Solution {
  public:
    int longestWPI(vector<int> &hours) {
        int n = hours.size();
        if (n == 1) {
            return hours[0] > 8;
        }
        for (auto &i : hours) {
            if (i > 8) {
                i = 1;
            } else {
                i = -1;
            }
        }
        // 计算新hours的前缀和
        vector<int> prefix(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + hours[i - 1];
        }
        //
        stack<int> l_stk;
        int res = 0;
        l_stk.push(0);
        for (int i = 1; i <= n; i++) {
            if (prefix[i] > 0) {
                res = std::max(res, i);
            }
            if (prefix[i] < prefix[l_stk.top()]) {
                l_stk.push(i);
            }
        }
        for (int r = n; r >= 1; r--) {
            while (!l_stk.empty() && prefix[r] > prefix[l_stk.top()]) {
                if (l_stk.empty()) {
                    return std::max(r, res);
                }
                res = std::max(res, r - l_stk.top());
                l_stk.pop();
            }
        }
        return res;
    }
};

Hash table

class Solution {
  public:
    int max(int a, int b) {
        return a > b ? a : b;
    }
    int longestWPI(vector<int> &hours) {
        int n = hours.size();
        for (auto &i : hours) {
            if (i > 8) {
                i = 1;
            } else {
                i = -1;
            }
        }
        // prefix sum of hours
        vector<int> prefix(n, 0);
        prefix[0] = hours[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + hours[i];
        }
        unordered_map<int, int> mp; 
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (prefix[i] > 0)
                res = max(res, i + 1);
            else {
                auto iter = mp.find(prefix[i] - 1);
                if (iter != mp.end()) {
                    res = max(res, i - iter->second);
                }
                if (mp.find(prefix[i]) == mp.end()) {
                    mp[prefix[i]] = i;
                }
            }
        }
        return res;
    }
};