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;
}
};
