[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element

不定長的 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;
    }
};