Re: [閒聊] 每日LeetCode已回收
2444. Count Subarrays With Fixed Bounds
給定一個陣列 nums 跟兩個整數 minK、maxK，
求有多少種 subarray 的最小值等於 minK 且最大值等於 maxK。
(subarray 是由 array 中一段連續的元素組成)
Example 1:
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation:
[1,3,5] 和 [1,3,5,2] 這兩個 subarray 滿足最大值是 5 且最小值是 2
Example 2:
Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation:
總共有 10 種 subarray，每一種都滿足最大值是 1 且最小值是 1
解題思路:
給的陣列大小最大到 10^5，一些 O(n^2) 的做法應該不會過，
要用一些 O(nlogn) 以下的做法來做，
其中一個作法是 sliding windows 可以做到線性時間。
用 L、R 來維護當前的區間 nums[L~R]，
當 nums[R] < minK 或 nums[R] > maxK 時，
因為符合條件的 subarray 不可能包含 nums[R]，
所以可以處理完 nums[L+1~R-1], nums[L+2~R-1], ..., nums[R-1~R-1] 後，
跳過 nums[R] 從 nums[R+1~R+1] 開始。
但是要快速的知道 nums[L~R-1] 有多少個答案，
我們必須要知道從哪個位置開始是答案，
假設 nums[L~i] 是答案則 nums[L~i], nums[L~i+1], ..., nums[L~R-1] 都會是答案，
因為 nums[i~R-1] 的元素全部都介於 [minK, maxK] (前面有檢查過的關係)，
就可以快速求得 nums[L~R-1] 這個區間的答案數量為 R-i。
我們還需要快速求得這個 i 是多少，
從 L 開始，i = max(下一個等於 minK 的位置, 下一個等於 maxK 的位置)，
可以用兩個 queue 來記錄等於 minK 的元素位置跟等於 maxK 的元素位置，
當 R 右移時檢查是否符合並 push 進 queue，
並且兩個 queue 都不為空時則 nums[L~R] 也是符合條件的答案，
當 L 右移時檢查是否超過 queue 的 front，如果超過則 pop，
並處理上述的過程。
C++ code:
class Solution {
public:
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
long long ans = 0;
queue<int> minidx, maxidx;
int l = 0, r = 0;
while(l < nums.size()){
if(r == nums.size() || nums[r] > maxK || nums[r] < minK){
l++;
if(l <= r){
if(minidx.size() > 0 && minidx.front() < l) minidx.pop();
if(maxidx.size() > 0 && maxidx.front() < l) maxidx.pop();
if(minidx.size() > 0 && maxidx.size() > 0){
int idx = max(minidx.front(), maxidx.front());
ans += r - idx;
}
}
else r++;
}
else if(r < nums.size()){
if(nums[r] == minK) minidx.push(r);
if(nums[r] == maxK) maxidx.push(r);
if(minidx.size() > 0 && maxidx.size() > 0) ans++;
r++;
}
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677894651.A.476.html
※ 編輯: idiont (140.113.229.216 臺灣), 03/04/2023 09:56:52
→
03/04 10:29,
2年前
, 1F
03/04 10:29, 1F
→
03/04 14:16,
2年前
, 2F
03/04 14:16, 2F
→
03/04 14:16,
2年前
, 3F
03/04 14:16, 3F
什麼意思 queue不是可以存多個元素 但每次都只看第一個嗎
好像有其他方法可以不用queue
但這是當時的第一直覺做法就這樣寫了
※ 編輯: idiont (140.113.229.216 臺灣), 03/04/2023 20:08:08
推
03/04 23:47,
2年前
, 4F
03/04 23:47, 4F
→
03/04 23:47,
2年前
, 5F
03/04 23:47, 5F
我當初想到的計算方法應該還是需要queue
沒辦法單靠兩個變數來存
大部分的答案計算都是L更新的時候在處理的
(以L為準計算有多少種右界符合)
要改的話要把他放到R更新的時候處理
(以R為準計算有多少種左界符合)
那應該像是另一種邏輯的計算方法
但確實就可以不用queue了
※ 編輯: idiont (140.113.229.216 臺灣), 03/05/2023 01:53:06
推
03/05 03:36,
2年前
, 6F
03/05 03:36, 6F
討論串 (同標題文章)
完整討論串 (本文為第 258 之 719 篇)：