349 words
2 minutes
Greedy&Linear Scan

This algorithm is a linear scan (one-pass) greedy counting algorithm.
- Linear Scan / One-pass Traversal
- Greedy (always keeps the best answer so far)
- Can also be seen as a simple state tracking approach
485. Max Consecutive Ones
Given a binary array nums, return the maximum number of consecutive 1’s in the array.
Example 1:
Input: nums = [1,1,0,1,1,1]Output: 3Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.Example 2:
Input: nums = [1,0,1,1,0,1]Output: 2Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: mx = 0 cnt = 0 for x in nums: if x == 1: cnt += 1 else: mx = max(mx, cnt) cnt = 0 mx = max(mx, cnt) return mxclass Solution {public: int findMaxConsecutiveOnes(vector<int>& nums) { int ans = 0; int cnt = 0; for (int x : nums) { if (x == 0) { ans = max(ans, cnt); cnt = 0; } else { cnt += 1; } } ans = max(ans, cnt); return ans; }};1446. Consecutive Characters
The power of the string is the maximum length of a non-empty substring that contains only one unique character.
Given a string s, return the power of s.
Example 1:
Input: s = "leetcode"Output: 2Explanation: The substring "ee" is of length 2 with the character 'e' only.Example 2:
Input: s = "abbcccddddeeeeedcba"Output: 5Explanation: The substring "eeeee" is of length 5 with the character 'e' only.Constraints:
1 <= s.length <= 500sconsists of only lowercase English letters.
class Solution: def maxPower(self, s: str) -> int: ans = 1 cnt = 1 for i in range(len(s)): if s[i] == s[i - 1]: cnt += 1 else: cnt = 1 ans = max(ans, cnt) return ansclass Solution {public: int maxPower(string s) { int ans = 0; int l = 0; int n = s.size(); map<char, int> cnt; for (int r = 0; r < n; r++) { cnt[s[r]]++; while (cnt.size() > 1) { cnt[s[l]]--; if (cnt[s[l]] == 0) { cnt.erase(s[l]); } l++; } ans = max(ans, r - l + 1); } return ans; }}; Greedy&Linear Scan
https://lxy-alexander.github.io/blog/posts/algorithm/greedylinear-scan/