贪心

副标题 / 摘要 最大子数组和是最经典的一维 DP / 贪心题。本文用 ACERS 模板拆解 Kadane 算法，给出工程迁移思路与多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、动态规划、贪心 SEO 关键词：Maximum Subarray, 最大子数组和, Kadane, 动态规划, O(n) 元描述：Kadane 一维 DP 求最大子数组和，含工程场景、复杂度分析与多语言代码。 目标读者 正在刷 Hot100 的学习者 想掌握“最大子段和”经典模板的中级开发者 需要做序列区间增益分析的工程师 背景 / 动机 最大子数组和不仅是 LeetCode 经典题，也常见于实际系统： 交易收益区间、指标提升区间、日志峰值段落、吞吐提升区间等都可以抽象为“最大连续收益”。 朴素 O(n^2) 枚举无法扩展，Kadane 给出 O(n) 的线性解。 核心概念 子数组：连续且非空的数组片段 状态转移：dp[i] 表示“以 i 结尾的最大子数组和” Kadane 思想：如果前缀和为负，直接丢弃，从当前位置重新开始 A — Algorithm（题目与算法） 题目还原 给你一个整数数组 nums，找出一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。 输入输出 名称 类型 描述 nums int[] 整数数组 返回 int 最大子数组和 示例 1（官方） nums = [-2,1,-3,4,-1,2,1,-5,4] 输出 = 6 解释：子数组 [4,-1,2,1] 和为 6 示例 2（官方） nums = [1] 输出 = 1 C — Concepts（核心思想） 关键公式 设 dp[i] 为以 i 结尾的最大子数组和： ...

副标题 / 摘要 固定间距 1 检测是典型的“事件间距校验”模型。本文按 ACERS 结构拆解题意、原理与工程迁移，并给出多语言可运行实现。 预计阅读时长：10~12 分钟 标签：数组、双指针、事件间距 SEO 关键词：固定间距 1 检测, 事件间距, LeetCode 1437, O(n) 元描述：一次扫描判断所有 1 是否至少相隔 k 个位置，含工程场景、复杂度对比与多语言代码。 目标读者 刷 LeetCode 并希望沉淀“模板题”的学习者 做监控/风控/行为分析的工程师 需要判断事件间隔是否合规的系统开发者 背景 / 动机 许多系统都有“事件不能过密”的约束：例如登录失败、报警事件、敏感操作、API 调用等。 这类问题的本质是 “事件间距是否满足阈值”，与该题完全等价。 如果能用 O(n) 一次扫描完成校验，就能直接迁移到实时系统。 核心概念 事件间距：两个事件之间至少有 k 个“空位” 在线校验：只记住上一次事件的位置即可 边界处理：初始化 last = -k-1，消除首个事件特判 A — Algorithm（题目与算法） 题目还原 给定整数数组 nums 与整数 k，若任意两个 1 之间至少有 k 个 0（等价于两次 1 的索引差 > k），返回 true，否则返回 false。 输入输出 名称 类型 描述 nums int[] 仅包含 0/1 的数组 k int 需要的最小间隔 返回 bool 是否满足间距约束 示例 1 nums = [1,0,0,0,1,0,0,1], k = 2 输出: true 示例 2 nums = [1,0,1], k = 2 输出: false C — Concepts（核心思想） 关键观察 只需要记住 上一个 1 的索引 last 当遇到新的 1：若 i - last <= k，说明间隔不足 否则更新 last = i 方法归类 单次线性扫描（One-pass Scan） 事件间距校验（Event Spacing Check） 双指针 / 贪心（Greedy with last pointer） 数学表达 若 i 和 j 是两个 1 的索引（i < j），要求： ...