leetcode/algorithms/max_consecutive_ones3.cpp at master · hanfezh/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 1004. Max Consecutive Ones III
// Refer: https://leetcode.com/problems/max-consecutive-ones-iii
// Author: xianfeng.zhu@gmail.com

#include <algorithm>
#include <tuple>
#include <vector>

#include "gtest/gtest.h"

// Sliding window, two pointers
class Solution {
 public:
  int longestOnes(std::vector<int>& nums, int k) {
    int prev = 0;
    int used_zeros = 0;
    int max_ones = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (nums[i] == 0) {
        used_zeros++;
      }
      while (used_zeros > k) {
        if (nums[prev] == 0) {
          used_zeros--;
        }
        prev++;
      }
      max_ones = std::max(max_ones, i - prev + 1);
    }
    return max_ones;
  }
};

TEST(Solution, longestOnes) {
  std::vector<std::tuple<std::vector<int>, int, int>> cases{
      {{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 2, 6},
      {{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 3, 10},
  };
  for (auto& [nums, k, max_ones] : cases) {
    EXPECT_EQ(Solution().longestOnes(nums, k), max_ones);
  }
}