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