郑州餐饮网站建设公司,怎样下载wordpress,做网站的框架,dw修改wordpress主题 Problem: 1493. 删掉一个元素以后全为 1 的最长子数组
1493. 删除一个元素以后全为1的最长子数组 - 题解 问题描述
给定一个二进制数组 nums#xff0c;你需要从中删除一个元素。请你在删掉元素后返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组 Problem: 1493. 删掉一个元素以后全为 1 的最长子数组
1493. 删除一个元素以后全为1的最长子数组 - 题解 问题描述
给定一个二进制数组 nums你需要从中删除一个元素。请你在删掉元素后返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组请返回 0。
示例 输入nums [1, 1, 0, 1] 输出3 删除位置 2 的元素后最长的子数组为 [1, 1, 1] 输入nums [0, 1, 1, 1, 0, 1, 1, 0, 1] 输出5 删除位置 4 的元素后最长的子数组为 [1, 1, 1, 1, 1]
解题思路
为了找到删除一个元素后最长的全 1 子数组我们可以使用滑动窗口的技术来高效地处理此问题。具体步骤如下 定义变量 n数组的大小。ans记录最长子数组的长度。left滑动窗口的左边界。cnt数组cnt[0] 用于计数 0 的个数cnt[1] 用于计数 1 的个数。 遍历数组 使用 right 作为滑动窗口的右边界遍历数组。每遇到一个 nums[right]更新计数器 cnt。 调整窗口 当窗口中 0 的数量大于 1 时移动左边界 left直到窗口中 0 的数量不超过 1。 更新结果 计算当前窗口的长度right - left并更新 ans。 返回结果 最后返回 ans并注意要减去 1因为我们删除了一个元素。
代码实现
以下是使用 C 实现的代码
class Solution {
public:int longestSubarray(vectorint nums) {int n nums.size(), ans 0, left 0;int cnt[2]{}; // cnt[0] 用于记录 0 的数量cnt[1] 用于记录 1 的数量for (int right 0; right n; right) {cnt[nums[right]]; // 更新当前数字的计数// 调整窗口的左边界while (cnt[0] 1) { // 如果 0 的数量超过 1cnt[nums[left]]--; // 移动左指针减少计数}ans max(ans, right - left); // 更新找到的最大长度}return ans; // 返回结果}
};复杂度分析
时间复杂度O(n)每个元素最多被访问两次一次由 right 指针另一次由 left 指针。空间复杂度O(1)只使用了常量空间来存储计数器 cnt。
总结
本题的关键在于灵活使用滑动窗口来处理动态变化的子数组长度。在窗口调整过程中需要合理管理 0 的数量从而确保我们能在删除一个元素后找到最长的全 1 子数组。通过此解法我们可以高效地解决问题并得到满意的结果。
