贪心|=转换

lc

lc992

妙妙题😋

等于 转 两至多作差win(k)-win(k-1)

class Solution {

public:

int subarraysWithKDistinct(vector<int>& nums, int k)

{

int n=nums.size();

auto win=[&](int k)->int

{

int l=0,ret=0;

unordered_map<int,int> hash;

for(int r=0;r<n;)

{

hash[nums[r]]++;

while((int)hash.size()>k)

{

if(--hash[nums[l]]==0)

hash.erase(nums[l]);

l++;

}

ret+=(r-l);

r++;

}

return ret;

};

return win(k)-win(k-1);

}

};

lc1580

先算出仓库每个位置能装的最大高度（左右两边推min的限制里取宽松的max）

把箱子和这些高度都排好序，小箱子挨个配小高度，能配多少算多少

class Solution {
public:
int maxBoxesInWarehouse(vector<int>& b, vector<int>& w)

{
int n = w.size();
vector<int> l(n), r(n), v(n);
l[0] = w[0];
for (int i = 1; i < n; ++i)

l[i] = min(l[i-1], w[i]);
r[n-1] = w[n-1];
for (int i = n-2; i >= 0; --i)

r[i] = min(r[i+1], w[i]);

for (int i = 0; i < n; ++i)

v[i] = max(l[i], r[i]);

sort(b.begin(), b.end());
sort(v.begin(), v.end());
int i = 0, c = 0;
for (int h : v)

if (i < b.size() && b[i] <= h) i++, c++;
return c;
}
};