Longest Subarray of 1's After Deleting One Element (LeetCode 1493)

Nguồn: LeetCode 1493 Độ khó: Trung bình Hai con trỏ Cửa sổ trượt Đếm

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

LeetCode 1493 – Longest Subarray of 1's After Deleting One Element (Dãy con toàn số 1 dài nhất sau khi xóa một phần tử) – độ khó Medium.

Cho một mảng nhị phân nums (chỉ gồm số 0 và số 1), bạn phải xóa một phần tử khỏi mảng.

Yêu cầu: trả về độ dài của dãy con liên tiếp khác rỗng dài nhất chỉ chứa số 1 trong mảng thu được. Trả về $0$ nếu không có dãy con nào như vậy.

Ràng buộc:

• $1 \le$ nums.length $\le 10^5$
• nums[i] là $0$ hoặc $1$.

Ví dụ 1:

Input: nums = [1,1,0,1]
Output: 3

Giải thích: sau khi xóa số ở vị trí 2, dãy [1,1,1] chứa 3 số 1.

Ví dụ 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5

Giải thích: sau khi xóa số ở vị trí 4, mảng thành [0,1,1,1,1,1,0,1], dãy con toàn số 1 dài nhất là [1,1,1,1,1].

Ví dụ 3:

Input: nums = [1,1,1]
Output: 2

Giải thích: bạn bắt buộc phải xóa một phần tử.

Ví dụ 4:

Input: nums = [1,1,0,0,1,1,1,0,1]
Output: 4

Ví dụ 5:

Input: nums = [0,0,0]
Output: 0

1493. Longest Subarray of 1's After Deleting One Element – Medium.

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Example 4:

Input: nums = [1,1,0,0,1,1,1,0,1]
Output: 4

Example 5:

Input: nums = [0,0,0]
Output: 0

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Về dữ liệu vào / ra của code trong bài

Trên LeetCode các bạn chỉ cần nộp phần class Solution. Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng 1 là số phần tử $n$, dòng 2 gồm $n$ số 0/1 của mảng nums; in ra một số nguyên là đáp án. Ví dụ 1 sẽ nhập là:

4
1 1 0 1

và chương trình in ra 3.

Tóm tắt đề bài: cho một dãy số $a$ gồm $N$ số, các số chỉ gồm số 0 hoặc số 1. Bạn được xóa duy nhất 1 số bất kì (và bắt buộc phải xóa). Hỏi cần chọn số nào để xóa để sau khi xóa, bạn được một dãy gồm các số 1 liên tục dài nhất. Trả về độ dài của dãy số 1 liên tục đó.

Ví dụ 2: [0,1,1,1,0,1,1,0,1]. Xóa số 0 ở vị trí 4 thì hai khúc 1,1,1 và 1,1 dính lại thành 5 số 1 liên tiếp. Ví dụ 3 thì mảng toàn số 1 nhưng vẫn bắt buộc xóa một số nên chỉ còn 2.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Thử xóa từng phần tử · O(n²) · TLECách 2Hai con trỏ (cách của mình) · O(n)

Cách 1Thử xóa từng phần tử – O(n²)

Làm đúng theo đề: thử xóa lần lượt từng phần tử del, rồi đi một vòng qua các phần tử còn lại để tìm dãy số 1 liên tiếp dài nhất (biến run tăng khi gặp số 1, về 0 khi gặp số 0). Có $n$ cách xóa, mỗi lần duyệt $O(n)$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestSubarray(vector<int>& a) {
        int n = (int) a.size();
        int ans = 0;
        for (int del = 0; del < n; del++) {      // thử xóa phần tử thứ del
            int run = 0;                         // độ dài dãy số 1 liên tiếp hiện tại
            for (int i = 0; i < n; i++) {
                if (i == del) continue;          // bỏ qua phần tử bị xóa
                if (a[i] == 1) {
                    run++;
                    ans = max(ans, run);
                }
                else {
                    run = 0;
                }
            }
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    Solution sol;
    cout << sol.longestSubarray(a);
    return 0;
}

import sys
from typing import List

class Solution:
    def longestSubarray(self, a: List[int]) -> int:
        n = len(a)
        ans = 0
        for d in range(n):                 # thử xóa phần tử thứ d
            run = 0                        # độ dài dãy số 1 liên tiếp hiện tại
            for i in range(n):
                if i == d:                 # bỏ qua phần tử bị xóa
                    continue
                if a[i] == 1:
                    run += 1
                    ans = max(ans, run)
                else:
                    run = 0
        return ans

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1 + n]]
    print(Solution().longestSubarray(a))

main()

Không gian$O(1)$

Thời gian$O(n^2)$

Bị TLE

Với $n = 10^5$ thì có $10^{10}$ phép tính, chắc chắn quá thời gian. Cách này chỉ để hiểu bài và làm code đối chiếu thôi các bạn nhé.

Cách 2Hai con trỏ – O(n)

Phương pháp giải: Two pointers (hai con trỏ).

Nhận xét

Một đoạn liên tiếp gồm tối đa 1 số 0 thì khi ta xóa 1 phần tử trong đoạn đó (xóa đúng số 0 nếu có, còn không thì xóa một số 1 bất kỳ), ta được toàn bộ đoạn gồm toàn số 1, độ dài giảm đi 1.

Vậy bài toán trở thành: tìm đoạn $[l..i]$ dài nhất chứa tối đa 1 số 0, đáp án là độ dài đoạn đó trừ 1, tức là $i - l$.

• Với mỗi giá trị $i$, ta gọi $l$ là vị trí xa $i$ nhất về phía bên trái sao cho số lượng số 0 trong đoạn $a[l..i]$ tối đa là 1.
• Gọi $cntZero$ là số lượng số 0 trong đoạn $[l..i]$. Ban đầu, ta khởi tạo $l = 0$.
• Với vị trí $i$ hiện tại, khi $a[i] = 0$, ta tăng $cntZero$ lên 1 đơn vị. Nếu $cntZero \gt 1$, ta tiến hành dịch $l$ lên: nếu $a[l] = 0$ thì ta giảm $cntZero$ xuống 1 đơn vị. Dịch $l$ cho đến khi $cntZero \le 1$.
• Như vậy đoạn $[l..i]$ là đoạn thỏa mãn, và vì phải xóa đi 1 phần tử trong đoạn $[l..i]$, ta cập nhật kết quả $ans = \max(ans, i - l)$.

Trường hợp đặc biệt tự động đúng

Mảng toàn số 1: đoạn $[0..n-1]$ không có số 0 nào, $ans = n - 1$ – đúng vì vẫn phải xóa một số. Mảng toàn số 0: mỗi đoạn hợp lệ chỉ dài 1, $ans = 0$. Không cần if-else gì thêm.

Minh hoạ cửa sổ trượt

Em nhập mảng 0/1 rồi bấm Tiếp. Ô xanh là số 1 trong cửa sổ, ô vàng là số 0 (sẽ bị xóa), ô đỏ là số 0 thứ hai làm cửa sổ "quá tải", ô mờ là ngoài cửa sổ:

nums

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestSubarray(vector<int>& a) {
        int cntZero = 0;
        int n = (int) a.size();
        int ans = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                cntZero++;
            }
            while (cntZero > 1) {
                if (a[l] == 0) {
                    cntZero--;
                }
                l++;
            }
            ans = max(ans, i - l);
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    Solution sol;
    cout << sol.longestSubarray(a);
    return 0;
}

import sys
from typing import List

class Solution:
    def longestSubarray(self, a: List[int]) -> int:
        cntZero = 0
        n = len(a)
        ans = 0
        l = 0
        for i in range(n):
            if a[i] == 0:
                cntZero += 1
            while cntZero > 1:
                if a[l] == 0:
                    cntZero -= 1
                l += 1
            # đoạn [l..i] có tối đa một số 0, xóa đi 1 phần tử còn i - l số
            ans = max(ans, i - l)
        return ans

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1 + n]]
    print(Solution().longestSubarray(a))

main()

C++▶ Chạy tay từng dòng codeHai con trỏ: giữ đoạn [l..i] có tối đa một số 0, đáp án i - l.

Dữ liệu vào (stdin) – sửa thoải mái4 1 1 0 1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4class Solution {

5public:

6 int longestSubarray(vector<int>& a) {

7 int cntZero = 0;

8 int n = (int) a.size();

9 int ans = 0;

10 int l = 0;

11 for (int i = 0; i < n; i++) {

12 if (a[i] == 0) {

13 cntZero++;

14 }

15 while (cntZero > 1) {

16 if (a[l] == 0) {

17 cntZero--;

18 }

19 l++;

20 }

21 ans = max(ans, i - l);

22 }

23 return ans;

24 }

25};

26

27int main() {

28 int n;

29 cin >> n;

30 vector<int> a(n);

31 for (int i = 0; i < n; i++) {

32 cin >> a[i];

33 }

34 Solution sol;

35 cout << sol.longestSubarray(a);

36 return 0;

37}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Thời gian: $i$ chạy $n$ lần, $l$ chỉ tăng chứ không bao giờ lùi nên tổng cộng cũng tăng không quá $n$ lần ⇒ $O(n)$.
• Không gian: chỉ dùng vài biến ⇒ $O(1)$ (không tính mảng đầu vào).

Không gian$O(1)$

Thời gian$O(n)$

Bài anh em

Đây chính là bài LeetCode 2024 – Maximize the Confusion of an Exam thu nhỏ: "đoạn dài nhất chứa không quá $k$ phần tử xấu" với $k = 1$, chỉ khác là phải trừ 1 vì bắt buộc xóa một phần tử.

Ghi chú của mình: code C++ và Python của cả 2 cách (đọc dữ liệu từ bàn phím như mô tả ở đầu bài) đã được kiểm tra với 5 ví dụ của đề và 500 bộ test ngẫu nhiên ($n \le 10$), so với code vét cạn thử xóa từng phần tử rồi xét mọi đoạn con – khớp hết. Với $n = 10^5$: cách 2 chạy dưới 0.1 giây cả C++ lẫn Python; cách 1 bản C++ với $n = 2 \cdot 10^4$ đã mất khoảng 0.6 giây, $n = 10^5$ sẽ chậm hơn cỡ 25 lần ⇒ TLE.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇