Prefix Sum & Difference Array & Two Pointer

頭尾固定的雙指針 –- sliding window

例題：sliding windows maxmium

詢問每個大小為 \(k\) 的 sliding windows (區間) 的最大值

\(-10^4 \le a_i \le 10^4\)

用 multiset 維護 sliding windows 內的數字

程式碼：

 vector<int> ret;
multiset<int> st;
for(int i = 0; i < k; i++) {
    st.insert(nums[i]);
}
ret.push_back(*(st.rbegin()));
for(int i = k; i < nums.size(); i++) {
    st.insert(nums[i]);
    st.erase(st.find(nums[i - k]));
    ret.push_back(*(st.rbegin()));
}
return ret;

也可以丟進 priority_queue 裡面(存 pair(value,index))，

每次查找最大值，檢查 index 是否是符合條件的，
若不符合就 pop 掉直到找到就好。

例題：

給一個長度為 \(n\)、由非負整數組成的陣列 \(a\)，在 \(\sum\limits^r_{i = l}a_i \le S\) 的情況下，最大化 \(r - l\)。

雙指針維護左界跟右界，被左界跟右界框起來的區域就是我們想要的，但是左界跟右界要怎麼移動呢？

每次將右界向右移動一格，並當總和超過 \(S\) 時，將左界也向右移動。

\(S = 20\)，初始化時，沒有包含任何區間。

\(l = 1, r = 1, sum \le 20, r++\)

\(l = 1, r = 2, sum \le 20, r++\)

\(l = 1, r = 3, sum \le 20, r++\)

\(l = 1, r = 4, sum \le 20, r++\)

\(l = 1, r = 5, sum > 20, l++\)

\(l = 2, r = 5, sum \le 20, r++\)

\(l = 2, r = 6, sum > 20, l++\)

\(l = 3, r = 6, sum > 20, l++\)

\(l = 4, r = 6, sum \le 20, r++\)

\(l = 4, r = 7, sum > 20, l++\)

\(l = 5, r = 7, sum > 20, l++\)

結束了

\(l\) 和 \(r\) 最多只會移動 \(n\) 步，複雜度 \(O(n)\)

程式碼：

 for(int i = 0; i < n; i++) {
	sum += arr[i];
	while(sum > s) {
		sum -= arr[l];
		l++;
	}
	ans = max(ans, i - l + 1);
}

改變一下問題

給一個長度為 \(n\)、由非負整數組成的陣列 \(a\)
有幾組 pair \((l、r)\)，符合 \(\sum\limits^r_{i = l}a_i \le S\)

再觀察一下上一題
對 \(r = 4\) 來說， \(l = 1, 2, 3, 4\) 都符合 \(\sum\limits^r_{i = l}a_i \le S\)

因此本題就是在上一題的基礎上，對每個右界計算有幾個左界可以符合條件。

程式碼：

 for(int i = 0; i < n; i++) {
	sum += arr[i];
	while(sum > s) {
		sum -= arr[l];
		l++;
	}
	ans += (i - l + 1);
}

遇到一個問題時，如果他是要求最好的區間或者是有幾個區間符合條件時，就可以考慮雙指針，至於指針要放哪，就要看題目而定了。

例題：Container With Most Water

給一個為 \(n\) 的陣列 \(arr\)

\(a_i\) 代表在 \(x = i\) 的位置有高度為 \(a_i\) 的垂直線，
選兩個位置 \(i、j\) 且 \(i < j\)，計算 \(\text{min}(a_i, a_j)\times (j - i)\) 的最大值

做法二：

一開始先將指針放在最左邊跟最右邊，並比較兩邊的值，將值較小的指針往中間移，因為對這個指針來說，另外一邊的指針移動對答案是沒有貢獻的

程式碼：

 int maxa = 0;
int l = 0, r = n - 1;
while(l < r) {
    maxa = max(maxa, (r - l) * min(arr[l], arr[r]));
    if(arr[l] < arr[r]) {
        l++;
    }
    else r--;
}

	for(int i=1;i<=q;i++){
	int l,r,ans=0;
	cin>>l>>r;
	for(int j=l;j<=r;j++){
	ans+=arr[j];
	}
	cout<<ans<<"\n";
	}

	int n,l,r,q;
	int arr[N]={},sum[N]={};
	cin>>n;
	for(int i=1;i<=n;i++){
	cin>>arr[i];
	sum[i]=sum[i-1]+arr[i];
	}
	cin>>q;
	for(int i=1;i<=q;i++){
	cin>>l>>r;
	cout<<sum[r]-sum[l-1]<<"\n";
	}

	int n,l,r,k,x;
	int arr[N]={},f[N]={};
	cin>>n;
	for(int i=1;i<=n;i++){
	cin>>arr[i];
	f[i]=arr[i]-arr[i-1];
	}
	cin>>k;
	for(int i=1;i<=k;i++){
	cin>>l>>r>>x;
	f[r+1]-=x,f[l]+=x;
	}