1124. 表现良好的最长时间段.md

1124. 表现良好的最长时间段

• 前缀和

function longestWPI(hours: number[]): number {
    let max: number = 0;

    for (let i = 0; i < hours.length; ++i) {
        const value: number = hours[i] > 8 ? 1 : -1;
        if (i) {
            hours[i] = hours[i - 1] + value;
        } else {
            hours[i] = value;
        }
    }

    for (let i = 0; i < hours.length; ++i) {
        for (let j = i; j < hours.length; ++j) {
            const value: number = i ? hours[j] - hours[i - 1] : hours[j];
            const length: number = j - i + 1;
            value > 0 && (max = Math.max(max, length));
        }
    }

    return max;
};

• 前缀和 + 哈希表

/**
 *
 * @complex T(n) / S(n)
 * @see https://leetcode-cn.com/problems/longest-well-performing-interval/solution/bie-gen-lao-fu-ti-shi-yao-dan-diao-zhan-by-li-zi-h/  
 * @param {number[]} hours
 * @return {*}  {number}
 */
function longestWPI(hours: number[]): number {
    let max: number = 0,
        current: number = 0;

    const map: Map<number, number> = new Map<number, number>();

    for (let i = 0; i < hours.length; ++i) {
        current += hours[i] > 8 ? 1 : -1;

        if (current > 0) {
            max = i + 1;
        } else {
            !map.has(current) && map.set(current, i);
            map.has(current - 1) && (max = Math.max(max, i - map.get(current - 1)));
        }
    }

    return max;
}