（leetcode算法题）3413. 收集连续 K 个袋子可以获得的最多硬币

这道题是 2271. 毯子覆盖的最多白色砖块数 的子题，但是针对那些状态进行分析呢？

        是像 2271 中那样考虑以每一个coins[i][1]作为连续袋子中最右边那个端点呢？

        还是考虑 以每一个coins[i][0]作为连续袋子中最左边那个端点呢？

答案是这两者都要考虑，而且最多硬币数量一定在这两种状态中出现，

以coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4为例

最大硬币的数量只有可能在上面那个蓝条或最下面那个蓝条中出现，不可能在中间那个蓝条中出现

// 3413. 收集连续 K 个袋子可以获得的最多硬币数量 和 2271. 毯子覆盖的最多白色砖块数
// 用相同的滑动窗口算法
class Solution {
using ll = long long;
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(), coins.end(), [&](vector<int>& v1, vector<int>& v2){
            return v1[0] < v2[0];            
        });
        int n = coins.size();
        ll ret = 0, left = 0, curcoins = 0;
        for(auto& bag : coins){
            ll bl = bag[0], br = bag[1], bagcoin = bag[2];
            curcoins += (br - bl + 1) * bagcoin;
            while(coins[left][1] < br - k + 1){
                curcoins -= ((ll)(coins[left][1] - coins[left][0] + 1) * (ll)coins[left][2]);
                left++;
            }
            ll disposecoins = max((ll)0, (ll)(br - k + 1 - coins[left][0]) * (ll)coins[left][2]);
            ret = max(ret, curcoins - disposecoins);
        }
        int right = n - 1;
        curcoins = 0;
        for(int j = n - 1; j >= 0; --j){
            ll bl = coins[j][0], br = coins[j][1], bagcoin = coins[j][2];
            curcoins += (br - bl + 1) * bagcoin;
            while(coins[right][0] > bl + k - 1){
                curcoins -= ((ll)(coins[right][1] - coins[right][0] + 1) * (ll)coins[right][2]);
                --right;
            }
            ll disposecoins = max((ll)0, (ll)(coins[right][1] - (bl + k - 1)) * (ll)coins[right][2]);
            ret = max(ret, curcoins - disposecoins);
        }
        return ret;
    }
};