題目

• 概述：給定一個整數(shù)數(shù)組，求出這個數(shù)組中良好的子數(shù)組的最大長度。良好的子數(shù)組定義如下：大于8的數(shù)的占比超過50%

• 輸入：整數(shù)數(shù)組，長度范圍[1, 10000]，每個數(shù)范圍[0, 16]

• 輸出：良好的子數(shù)組的最大長度

• 出處：https://leetcode-cn.com/problems/longest-well-performing-interval/

思路

• 參考 劉岳 https://leetcode-cn.com/problems/longest-well-performing-interval/solution/qian-zhui-he-dan-diao-zhan-python3-by-smoon1989/
• 對于本題來說，8是一個分界點，所以小于等于8的數(shù)之間沒有差別，大于8的數(shù)也沒有差別，所以可以把小于等于8的數(shù)看作-1，大于8的數(shù)看作1，那么本題可以轉(zhuǎn)化為求所有元素和大于0的子數(shù)組中最長的子數(shù)組
• 將數(shù)組分解為以索引x為終點的子數(shù)組(x屬于[0,n-1],設(shè)數(shù)組長度為n)，先求以索引x為終點的子數(shù)組的最優(yōu)解，然后綜合這些最優(yōu)解可以得到最終答案
• 求以索引x為終點的子數(shù)組的解，可以先將數(shù)組求前綴和，得到一個前綴和數(shù)組，前綴和數(shù)組中后一個索引位置的數(shù)減去前一個索引位置的數(shù)大于0表示一個解，綜合所有解可以得到以索引x為終點的子數(shù)組的最優(yōu)解（索引差距最大的）
• 問題的關(guān)鍵在于如何快速找到這個索引差距最大的最優(yōu)解，可以先找終點x左邊最小的數(shù)，然后從該最小的數(shù)開始，遞歸地找左邊比它大的第一個數(shù)，直到無解
• 找左邊比它大的第一個數(shù)可以用單調(diào)棧這一數(shù)據(jù)結(jié)構(gòu)解決，這里適用的是單調(diào)遞減棧（構(gòu)造過程中沒有元素彈出，棧為空或當(dāng)前數(shù)小于棧頂元素時，當(dāng)前數(shù)入棧）
• 求解索引x-1為終點的子數(shù)組的最優(yōu)解可以繼承求解索引x為終點的子數(shù)組的最優(yōu)解用到的單調(diào)棧，因為以被彈出的元素為起點的解以索引x為終點總比以索引x-1為終點更優(yōu)(長度增加了1)

代碼

class Solution {
    public int longestWPI(int[] hours) {
        
        int len = hours.length;
        int[] preSums = new int[len + 1];
        preSums[0] = 0;
        for (int i = 1; i <= len; ++i) {
            preSums[i] = preSums[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
        }
        
        // stack stores index & index starts with 0
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i <= len; ++i) {
            if (stack.isEmpty() || preSums[i] < preSums[stack.peek()]) {
                stack.push(i);
            }
        }
        
        // use i > res optimize
        int res = 0;
        for (int i = len; i > res; --i) {
            while (!stack.isEmpty() && preSums[stack.peek()] < preSums[i]) {
                res = Math.max(res, i - stack.pop());
            }
        }
        
        return res;
        
    }
}