I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1004. Max Consecutive Ones III, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- Two pointers, sliding window
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are longestOnes.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//Two pointers, sliding window
02//Runtime: 60 ms, faster than 67.45% of C++ online submissions for Max Consecutive Ones III.
03//Memory Usage: 13 MB, less than 100.00% of C++ online submissions for Max Consecutive Ones III.
04/*
05Hints:
06One thing's for sure, we will only flip a zero if it extends an existing window of 1s. Otherwise, there's no point in doing it, right? Think Sliding Window!
07Since we know this problem can be solved using the sliding window construct, we might as well focus in that direction for hints. Basically, in a given window, we can never have > K zeros, right?
08We don't have a fixed size window in this case. The window size can grow and shrink depending upon the number of zeros we have (we don't actually have to flip the zeros here!).
09The way to shrink or expand a window would be based on the number of zeros that can still be flipped and so on.
10*/
11class Solution {
12public:
13 int longestOnes(vector<int>& A, int K) {
14 int left = 0, right = 0;
15 int N = A.size();
16 int ans = 0;
17 int used = 0;
18
19 while(right < N){
20 if(left > 0 && A[left-1] == 0){
21 used--;
22 }
23 //continue to look ahead when the A[right] is 1
24 //, or A[right] is 0 but we still have quota to use
25 while(right < N && (A[right] == 1 || used < K)){
26 if(A[right] == 0 && used < K){
27 used++;
28 }
29 right++;
30 }
31 // cout << "[" << left << "," << right-1 << "]" << endl;
32 ans = max(ans, right-left);
33 left++;
34 }
35 return ans;
36 }
37};
38
39//sliding window
40//not understand
41//https://leetcode.com/problems/max-consecutive-ones-iii/discuss/247564/JavaC%2B%2BPython-Sliding-Window
42//Runtime: 188 ms, faster than 15.66% of C++ online submissions for Max Consecutive Ones III.
43//Memory Usage: 55.5 MB, less than 50.08% of C++ online submissions for Max Consecutive Ones III.
44class Solution {
45public:
46 int longestOnes(vector<int>& A, int K) {
47 int slow, fast;
48
49 /*
50 slow and fast are not exact index to the array,
51 they only specify the size of the window
52 in the process, we will continue to find a bigger window,
53 if we find one, we will carry this window forward until
54 we find a larger one
55 */
56 for(slow = 0, fast = 0; fast < A.size(); ++fast){
57 if(A[fast] == 0) --K;
58 // cout << "[" << slow << ", " << fast << "], K: " << K << endl;
59 /*
60 only when K >= 0,
61 it's in a valid state,
62 so when K < 0,
63 slow will be moved forward, too
64 so the window will be carried foward
65
66 and if A[slow] is 0,
67 we and increase K back
68 */
69 if(K < 0 && A[slow++] == 0) ++K;
70 }
71
72 return fast - slow;
73 }
74};Cost