天池 在线编程 区间统计（队列）

样例 1:
输入: arr = [0, 0, 1, 0, 1, 1, 0], k = 1
输出: 7
解释: [0, 0], [1, 1], [3, 3], [6, 6], [0, 1], [0, 3], [1, 3] 
(区间 [i，j] 表示下标 i（包括）和下标 j（包括）之间的元素)

样例 2:
输入: arr = [1, 1, 1, 0, 0, 1], k = 2
输出: 3
解释: [3, 3], [4, 4], [3, 4] 
(区间 [i，j] 表示下标 i（包括）和下标 j（包括）之间的元素)

class Solution {
public:
    /**
     * @param arr: the 01 array
     * @param k: the limit 
     * @return: the sum of the interval
     */
    long long intervalStatistics(vector<int> &arr, int k) {
        // Write your code here.
        queue<int> q;
        int s = 0;
        long long ans = 0;
        for(int i = 0; i < arr.size(); ++i)
        {
        	q.push(i);
        	if(arr[i])
        		s++;
        	else//等于0，以该0为右端点的区间
        	{
	        	while(s > k || arr[q.front()]==1)//直到 s <= k 且 左端出现 0
	        	{
	        		if(arr[q.front()]==1)
	        			s--;
	        		q.pop();
	        	}
	        	ans += i-q.front()+1 - s;//区间的长度 减去 和 s 就是零的个数
	        }
        }
        return ans;
    }
};