- 不定長的 Sliding Window 套 pattern
class IWindow {
public:
virtual void add(int& num) = 0;
virtual void erase(int& num) = 0;
virtual bool check(int& num) = 0;
virtual ~IWindow() {}
};
class Window : public IWindow {
private:
int cnt = 0;
public:
Window() {}
void add(int& num) override {
if (num == 0) cnt++;
}
void erase(int& num) override {
if (num == 0) cnt--;
}
bool check(int& num) override {
return num == 0 && cnt == 1;
}
};
class Solution {
private:
unique_ptr<IWindow> _w;
public:
Solution(): _w(make_unique<Window>()) {}
int longestSubarray(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
int res = 0;
while (right < n) {
int num = nums[right++];
while (_w->check(num)) _w->erase(nums[left++]);
_w->add(num);
res = max(res, right-left-1);
}
return res;
}
};
- 但其實在 check & 移動左指標這一步可以做優化,左指標可以透過記錄一下一個合法的位置來快速移動。
class Solution {
private:
int last = 0;
public:
int longestSubarray(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
int res = 0;
while (right < n) {
int num = nums[right++];
if (num == 0) {
left = last;
last = right;
}
res = max(res, right-left-1);
}
return res;
}
};