正反两次扫描

lc3796

正反两次扫描

class Solution {

public:
int findMaxVal(int n, vector<vector<int>>& restrictions, vector<int>& diff) {
vector<int> max_val(n, INT_MAX);
for (auto& r : restrictions)
max_val[r[0]] = r[1];

vector<int> a(n);
for (int i = 0; i < n - 1; i++) {
a[i + 1] = min(a[i] + diff[i], max_val[i + 1]);
}
for (int i = n - 2; i > 0; i--) {
a[i] = min(a[i], a[i + 1] + diff[i]);
}
return ranges::max(a);
}
};

lc3795

hash+滑窗

class Solution {
public:
int minLength(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
int sum = 0;
int left = 0;
int ans = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
// 1. 入
int x = nums[i];
cnt[x]++;
if (cnt[x] == 1)
sum += x;

while (sum >= k) {
// 2. 更新答案
ans = min(ans, i - left + 1);
// 3. 出
int out = nums[left];
cnt[out]--;
if (cnt[out] == 0)
sum -= out;

left++;
}
}

return ans == INT_MAX ? -1 : ans;
}
};