前缀和.md

前缀和

对于一个数组arr，长度为n。定义一个新数组preSum，长度为n+1，用于表示该数组的前缀和。第一项为0，常用于一些判断子序列性质的题目。

题目：给你一份工作时间表hours，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。请你返回「表现良好时间段」的最大长度。

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

解法一

分析：所谓的表现良好的时间段，就是要求一个子序列中工作时间大于8小时的超过工作时间小雨8小时的时间段。既然是子序列性质的题目，可以转化为前缀和来做。将工作时间超过8的时间记为+1，工作时间小于8小时的时间记为-1。那么符合题目要求的子序列的和一定是严格大于0的。

将数组表示为前缀和数组后，可以很方便的求出某个子序列的和。要求某个子序列的和就是在第i个位置的前缀和减去第j个位置的前缀和。上面数组处理之后的前缀和数组为preSum=[0,1,2,1,0,-1,-2,1]。

题目转化为求preSum为正数的子序列最长长度。

• 暴力法：双层循环，

for(int i = 0; i < preSum.size();i++){
    for(int j = i+1; j < preSum.size();j++){
        if(preSum[j] - preSum[i] > 0){  //相减即代表i到j之间的子序列和
            //由于j和i是preSum中的下标，i是从一个没意义的值开始，因此j-i不需要加1，如i=0是，j=i，相减即代表原数组的第一个值，时间段长度为1
            ans = max(ans,j-i);
        }
    }
}

• 优化：从后往前

//因为从后往前，固定i，如果j满足条件，那么j之前的值可以不用考虑，肯定不会比j这个时间段长。
for(int i = 0; i < preSum.size();i++){
    for(int j = preSum.size()-1;j>i;j++){
        if(preSum[j] = preSum[i] > 0){
            ans = max(ans,j-i);
            continue;
        }
    }
}

• 进一步优化：使用单调递减的栈

//[0,-1,-2]
//上一步中，每次j需要从数组末尾开始重新遍历，维护一个严格递减的栈，因为j从末尾开始，如果j小于栈顶元素，那么肯定也小于栈中的其他元素，即这个j对所有的i都不满足条件。如果j大于栈顶元素，因为不在这个栈中的元素都是小于栈顶元素的，对这个j栈中的元素才是最长的。
stack<int> s;
int j = preSum.size()-1;
while(!s.empty() && j >= 0){
    if(preSum[j] > preSum[s.top()]){
        ans = max (j-s.top() , ans );
        s.pop();
    }else{
        j--;
    }
}

时间复杂度： O(N^2)，以上优化方法并没有减小时间复杂度，只是循环次数上的优化。

代码：

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int length = hours.size();
        int ans = 0;
        vector<int> preSum(length+1,0);
        for(int i = 0; i < length; i++){
            preSum[i+1] = preSum[i]+(hours[i]>8?1:-1);
        } 
        stack<int> s;
        s.push(0);
        for(int i = 1; i <= length; i++){
            if(preSum[i] < preSum[s.top()]){
                s.push(i);
            }
        }
        int end = length;
        while(!s.empty() && end >= 0){
            if(preSum[end] > preSum[s.top()]){
                ans = end-s.top() > ans ?  end-s.top() : ans;
                s.pop();
            }else{
                end--;
            }
        }
        return ans;
    }
};

解法二

分析：同样是基于前缀和，用一个变量cur记录前缀和，当cur>8时，cur++，否则cur--。从前往后遍历，如果cur>0，说明从开始到现在满足条件，res=i+1。当cur<=0时，用一个字典记录cur<0时的最小下标，即如果在后续碰到了这个cur就不更新，否则把这个下标记录下来。然后在字典中找cur-1的下标j，说明0到j的前缀和是cur-1，那么j到i的和为1，说明j+1到i的表现肯定是满足的，又由于保存的是最小的下标，所以肯定是最长的。只需要找cur-1的原因是因为hashmap中存的值是从0开始递减的，又因为存储的是最小的下标，所以一定是先存着cur-1的，cur-2如果存在也一定在其右边，因此只需要找cur-1的下标即可。

时间复杂度： O(N)

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();

        unordered_map<int, int> count;
        int cur = 0;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (hours[i] > 8) {
                cur++;
            } else {
                cur--;
            }
            if (cur > 0) res = i + 1;
            else {
                if (count.count(cur-1) > 0) res = max(res, i - count[cur-1]);
                if (count.count(cur) < 1) count[cur] = i;
            }
        }
        return res;

    }
};