題目描述

給你一份工作時間表 hours，上面記錄著某一位員工每天的工作小時數(shù)。

我們認為當員工一天中的工作小時數(shù)大于 8 小時的時候，那么這一天就是「勞累的一天」。

所謂「表現(xiàn)良好的時間段」，意味在這段時間內(nèi)，「勞累的天數(shù)」是嚴格 大于「不勞累的天數(shù)」。

請你返回「表現(xiàn)良好時間段」的最大長度。

題目解析

1. 轉(zhuǎn)變hours數(shù)組將符合勞累置為1, 不符合置為0
2. 再次更新數(shù)組轉(zhuǎn)變?yōu)榍熬Y和。
3. 求A[j] - A[i] > 0的最大距離，使用單調(diào)棧進行求和（單調(diào)遞減）。

C++代碼

    int longestWPI(vector<int>& hours) {
        vector<int> nh;
        nh.push_back(0);
        for(int i = 0; i < hours.size();i++) {
            if(hours[i] >= 9)
                nh.push_back(1);
            else
                nh.push_back(-1);
        }
        int sum = 0;
        stack<int> st;
        st.push(0);
        for(int i = 1; i < nh.size();i++) {
            sum += nh[i];
            nh[i] = sum;
            if(sum < nh[st.top()]) {
                st.push(i);
            }
                
        }
        int ans = 0;
        for(int i = nh.size()-1; i>=0; i--) {
            while(st.size() > 0 && nh[i] - nh[st.top()] > 0) {
                ans = max(ans, i - st.top());                  
                st.pop();
            }
            
            
        }
        return ans;
    }