1493. 删掉一个元素以后全为 1 的最长子数组

解法

滑动窗口

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
43
44
45
46
47
48
        
//核心是 每一次都已遇见0都会默认删除，记录遇见的0的数量， 当滑动窗口内的0数量超过一个，，就会去缩减左边界，抛弃掉上一次删除的0就可以对新加入的0进行 删除操作，非常巧妙 000111011110111111，
int ans = 0, n = nums.size();
        // cnt数组记录区间[j, i]中0和1的数量
        int cnt[2] = {0};
        for(int i = 0, j = 0; i < n; ++i) {
            cnt[nums[i]]++;
            // 缩小左端点j
            while(cnt[0] > 1) cnt[nums[j++]]--;
            // 必须删除一个元素，所以最终长度是i - j 而不是 i - j + 1
            ans = max(ans, i - j);
        }
        return ans;
        

     //下面的是我本来的解法，和之前的区别在于只有一个 删除0 的标记，第二次遇见就会忽略，这可以在一定程序上解决连续0的问题，但是对于0111101111110111，这种问题就无能为力了
     //滑动窗口运行
	bool isDel = false; //确定是否删除内容，表现在结果上就是最后的结果-1

	int left = 0, right = 0;
	int res = 0;
	int n = nums.size();

	for (int i = 0; i < n; i++)
	{
		if (nums[i] == 0)
		{
			if (!isDel)
			{
				++right;
				isDel = true;
			}
			else
			{
				res = max(right - left, res);
				left = right;
				isDel = false;
			}
		}
		else
		{
			++right;
		}
	}

	if (res == 0) res = right - left;
	return res - 1;

递推写法

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
43
44
45
    //递推写法
	int n = nums.size();
	vector<int> pre(n), suf(n);
 
//采用枚举一个点位的方式，动态规划的思想无非就是 选或者不选、枚举 这两种，这种都是要求对子问题的要一致，使用 选或不选 子问题就不一致了，多了一个可以删除一个点的 条件，一个子问题使用后，另一个子问题就需要考虑，不合适。
//这个解法是使用枚举，枚举到的点就是要被删除的点，周围的是能计入结果的长度。
	pre[0] = nums[0];
	for (int i = 1; i < n; ++i) {
		pre[i] = nums[i] ? pre[i - 1] + 1 : 0; //枚举到的点要被删除，因此除这以外遇见0都需要将和标记为0
	}

	suf[n - 1] = nums[n - 1];
	for (int i = n - 2; i >= 0; --i) {
		suf[i] = nums[i] ? suf[i + 1] + 1 : 0;
	}
 
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		int preVal = i == 0 ? 0 : pre[i - 1];
		int sufVal = i == n - 1 ? 0 : suf[i + 1];
		res = max(res,preVal + sufVal);
	}
 
	return res;

//递推优化
  int ans = 0;
        int p0 = 0, p1 = 0;
        for (int num: nums) {
            if (num == 0) {
                p1 = p0;
                p0 = 0;
            }
            else {
                ++p0;
                ++p1;
            }
            ans = max(ans, p1);
        }
        if (ans == nums.size()) {
            --ans;
        }
        return ans;

递推优化的推导过程

image-20240815181457099