推 idiont: 好酷的做法 而且還是 O(1) space 03/04 10:17
推 dannyko: 大師 03/04 11:03
推 NTHUlagka: 大師 有趣的做法 雖然好像官方的還是比較直觀XD 03/04 12:57
2444. Count Subarrays With Fixed Bounds
寫完才發現是以前寫過的題目
剛好可以拿來比較
結果還真的是用不同的寫法
上一次寫時用的是和官方參考解答一樣
存最近一次的
1. 在範圍之外的 index --> i_invalid
2. 恰為 minK 的 index --> i_min
3. 恰為 maxL 的 index --> i_max
這樣以當下 index 為結尾的合法 subarray 數量就是 min(i_min, i_max) - i_invalid
不過這次過了好幾個月再寫就有點不太一樣
我這次用的是寫一個 function f(L, R)
計算所有值都 >= L 且 <= R 的 subarray 數量
這樣以當下 index 為結尾的這種 subarray 的數量就是
當下 index - 上一次的非法 index，因為在這中間的 subarray 都是合法的
最後用排容原理計算
f(minK, maxK)
- f(minK + 1, maxK)
- f(minK, maxK - 1)
+ f(minK + 1, maxK - 1)
就會是答案
雖然總共要跑四次，但感覺比較不容易出錯？
class Solution {
public:
int64_t f(vector<int>& nums, int L, int R) {
int n = nums.size();
int64_t left = 0, ret = 0;
for (int right = 0; right < n; right++) {
int x = nums[right];
if (x < L || x > R) left = right + 1;
ret += right - left + 1;
}
return ret;
}
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
return f(nums, minK, maxK) - f(nums, minK + 1, maxK) -
f(nums, minK, maxK - 1) + f(nums, minK + 1, maxK - 1);
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677895116.A.646.html