Leetcode 1004. 最大连续1的个数 III（DAY 180）---- 二分查找学习期

偏执的太偏执、 2022-09-14 06:25 163阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解 queue 空间复杂度高）
     *  代码实现（首刷自解 O(1)空间）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解 queue 空间复杂度高） ##

--------------------

class Solution { 
    public:
        int longestOnes(vector<int>& nums, int k) { 
            int ret = 0,start = 0,end = 0;
            queue<int> one_input;
            while(end != nums.size())
            { 
                if(nums[end] == 0)
                    one_input.emplace(end);
                while(one_input.size() > k)
                { 
                    if(start == one_input.front())  one_input.pop();
                    ++start;
                }
                ++end;   
                ret = max(end - start,ret);
            }
    
            return ret;
        }
    };

--------------------

## 代码实现（首刷自解 O(1)空间） ##

--------------------

class Solution { 
    public:
        int longestOnes(vector<int>& nums, int k) { 
            int ret = 0,start = 0,end = 0;
            int one_input = 0;
            while(end != nums.size())
            { 
                if(nums[end] == 0)
                    ++one_input;
                while(one_input > k)
                { 
                    if(nums[start] == 0)  --one_input;
                    ++start;
                }
                ++end;   
                ret = max(end - start,ret);
            }
    
            return ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7f0f704c879544d991b9ae83cd1f1f88.png