3430.
Q4.
刚刚洗澡洗一洗突然想到怎么写
用了一个像是KMP的怪方法
对每个数找左右range
原本以为这一步是关键
写出来之后在count个数那边卡了好久==
range都查完了
被关太久了
怎么连数数都不会哇啊啊啊啊
去你妈的城市海巡数数仔
终于出来了2020
勾手指算的都是对的
写成式子就一直错呜呜呜呜
后面还是拆开来分开加
后来看别人写的都好干净漂亮
什么deque monostack 我都不会
我就这样了
感觉20天好像也是一下就过了
https://i.imgur.com/NlXcxaU.jpeg
using ll = long long;
class Solution {
public:
long long minMaxSubarraySum(vector<int>& nums, int k) {
int n = nums.size();
ll res = 0;
// 1 3 5 4 6 7 2 8, k = 4
vector<pair<int, int>> mi_range(n), mx_range(n);
for(int i = 0; i < n; i++){
mi_range[i] = {i, i};
mx_range[i] = {i, i};
}
// [limit, rimit]
// if same value, choose small idx
// left to right, min range
for(int i = 1; i < n; i++){
int limit = i - k + 1;
int pos = i;
while(limit <= (pos-1) and 0 <= (pos-1) and nums[pos-1] > nums[i]){
pos = mi_range[pos-1].first;
}
mi_range[i].first = max(pos, limit);
}
// right to left, min range
for(int i = n-2; i >= 0; i