10.4K 779 121

Đã đăng vào thg 8 2, 8:30 SA 15 phút đọc

201

Kĩ thuật stack đơn điệu

I. Giới thiệu chung

Trong các chuyên đề trước, tôi đã giới thiệu tới các bạn rất chi tiết về ngăn xếp và hàng đợi, cũng như cách cài đặt và sử dụng chúng trong lập trình. Tuy nhiên, các bài tập vẫn chỉ ở mức độ rất cơ bản, chưa có tính đặc trưng của cấu trúc dữ liệu. Trong chuyên đề này, chúng ta sẽ cùng thảo luận về một ứng dụng cực kỳ quan trọng của ngăn xếp, đó là Ngăn xếp đơn điệu.

Đúng như tên gọi của mình, ngăn xếp đơn điệu là một ngăn xếp được cài đặt sao cho các phần tử của nó được sắp xếp thành một dãy đơn điệu tăng, hoặc đơn điệu giảm từ đáy tới đỉnh ngăn xếp.

Một stack đơn điệu giảm

Để cài đặt được stack đơn điệu, thì thông thường, trước khi thêm một phần tử $x$ vào stack, người ta thường có thao tác "lọc lại stack". Dưới đây giả sử đang cần xây dựng một stack đơn điệu giảm, mã giả như sau:

{Chuẩn_bị_thêm_x_vào_stack}:
    while (not stack.empty()) and (stack.top() <= x):
        stack.pop();
    
    stack.push(x);

Bây giờ, hãy cùng đi vào phân tích một số bài toán kinh điển để hiểu hơn về cách áp dụng stack đơn điệu trong lập trình thi đấu!

II. Một số bài toán minh họa

1. Số kế tiếp

Đề bài

Cho một số nguyên gồm $n$ chữ số $d_1, d_2, \dots, d_n;$ ban đầu các chữ số của số đó được thể hiện theo đúng thứ tự từ $d_1$ tới $d_n$ . Số kế tiếp của $n$ là số mà chỉ bao gồm các chữ số $d_1, d_2, \dots, d_n$ nhưng lại lớn hơn $n$ và là nhỏ nhất có thể.

Hãy tìm số kế tiếp của số ban đầu?

Input:

Dòng đầu tiên chứa số nguyên dương $T$ - số lượng test cases.
$T$ $T$ nhóm dòng tiếp theo, mỗi nhóm dòng chứa một test case cấu trúc như sau:
- Dòng đầu tiên chứa số nguyên dương $n$ - số lượng chữ số.
- Dòng thứ hai chứa $n$ chữ số $d_1, d_2, \dots, d_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

$1 \le T \le 100$ .
$1 \le n \le 10^5$ .
$0 \le d_i \le 9; \forall i: 1 \le i \le n; d_1 \ne 0$ .

Output:

Trên $T$ dòng, mỗi dòng in ra một số nguyên là số kế tiếp của số đã cho trong test case tương ứng. Trong trường hợp không tìm được số kế tiếp, in ra $-1$ .

Sample Input:

2
5
1 5 4 8 3
10
1 4 7 4 5 8 4 1 2 6

Sample Output:

15834
1474584162

Ý tưởng

Giải thuật ngây thơ

Đối với $n$ nhỏ, ta hoàn toàn có thể sử dụng quay lui để tìm tất cả các hoán vị của $n$ chữ số, rồi từ đó tìm ra số nhỏ nhất lớn hơn số ban đầu. Cách làm này có độ phức tạp $O(n!)$ .

Cải tiến

Để cải tiến, ta nhận xét như sau: Nếu các chữ số của số ban đầu tạo thành một dãy giảm dần từ trái qua phải, thì chắc chắn không tồn tại số kế tiếp, vì số này đã là lớn nhất. Khi đó kết quả là $-1$ .

Còn ngược lại, thì chắc chắn việc biến đổi phải xảy ra ở một vị trí $p$ đầu tiên tính từ bên phải sang mà $d_p < d_{p + 1}$ (để số mới tạo thành là nhỏ nhất có thể nhưng vẫn lớn hơn số ban đầu).

Ta có thể sử dụng ngăn xếp để tìm vị trí $p$ này: Duyệt các vị trí $i$ từ $n$ về $1,$ thêm các chữ số $d_i$ vào ngăn xếp sao cho tạo thành một ngăn xếp đơn điệu tăng.

Nếu như thêm chữ số $d_i$ vào stack mà khiến cho stack bị vi phạm quy tắc đơn điệu tăng, tức là vị trí $i$ chính là vị trí cần thực hiện thay đổi (hay $p = i$ ). Ta hoán đổi chữ số $d_p$ với chữ số nhỏ nhất lớn hơn nó mà đứng sau nó, lúc này đã chắc chắn tạo được một số lớn hơn số ban đầu.

Tuy nhiên, ta lại mong muốn số mới thu được phải là nhỏ nhất có thể, vậy ta sắp xếp tăng dần các chữ số $d_{p + 1}...d_n$ .

Độ phức tạp

Cần phải sắp xếp lại các chữ số ở cuối, nên độ phức tạp tổng quát vẫn là $O\big(n \times \log(n) \big)$ .

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>
#define int long long
#define task "just_next."

using namespace std;

// Nhập dữ liệu cho từng truy vấn.
void enter(int &n, vector < int > &digits)
{
    cin >> n;

    digits.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> digits[i];
}

// Trả lời các truy vấn.
void query(int n, vector < int > &digits)
{
    stack < int > st;

    int p1 = 0, p2 = 0;
    for (int i = n; i >= 1; --i)
    {
        if (st.empty())
            st.push(i);
        else
        {
            if (digits[st.top()] > digits[i])
            {
                // Vị trí i chính là vị trí cần tác động.
                p1 = i;

                while (!st.empty() && digits[st.top()] > digits[i])
                {
                    // Lưu vị trí số nhỏ nhất lớn hơn d[p1].
                    p2 = st.top();
                    st.pop();
                }

                break;
            }
            else
                st.push(i);
        }
    }

    if (p1 == 0)
        cout << -1 << endl;
    else
    {
        swap(digits[p1], digits[p2]);
        sort(digits.begin() + p1 + 1, digits.end());

        for (int i = 1; i <= n; ++i)
            cout << digits[i];
        cout << endl;
    }
}

void solution()
{
    int t;
    cin >> t;

    while (t--)
    {
        int n;
        vector < int > digits;

        enter(n, digits);
        query(n, digits);
    }
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    solution();

    return 0;
}

Ngôn ngữ Python:

# Nhập dữ liệu.
def enter():
    n = int(input())
    digits = [int(i) for i in input().split()]

    return n, digits


# Trả lời truy vấn.
def query(n, digits):
    st = []  # Sử dụng list để cài đặt stack.

    p1, p2 = -1, -1
    for i in range(n - 1, -1, -1):
        if len(st) == 0:
            st.append(i)
        else:
            if digits[st[-1]] > digits[i]:
                p1 = i

                while len(st) > 0 and digits[st[-1]] > digits[i]:
                    p2 = st[-1]
                    st.pop()

                break
            else:
                st.append(i)

    digits[p1], digits[p2] = digits[p2], digits[p1]
    digits = digits[:(p1 + 1)] + sorted(digits[(p1 + 1):])

    print(*digits, sep='')


# Nhập nhiều test cases.
def main():
    t = int(input())

    for _ in range(t):
        n, digits = enter()
        query(n, digits)


if __name__ == '__main__':
    main()

2. Chênh lệch nhỏ nhất

Đề bài

Cho dãy số $A$ gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ . Với mỗi cặp số $(a_i, a_j)$ trong dãy, ta gọi chênh lệch giữa chúng là giá trị $|i - j|$ .

Bài toán đặt ra là với mỗi $a_i$ trong dãy, hãy xác định $a_j$ sao cho $a_j > a_i$ và chênh lệch giữa chúng là nhỏ nhất?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ - số lượng phần tử của dãy số.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

$1 \le n \le 10^6$ .
$1 \le a_i \le 10^9; \forall i: 1 \le i \le n$ .

Output:

Ứng với mỗi $a_i,$ đưa ra chỉ số $j$ của phần tử $a_j$ tìm được. Nếu tìm được nhiều chỉ số như vậy thì ưu tiên chỉ số nhỏ nhất. Còn nếu không tìm được thì đưa ra $-1$ .

Sample Input:

6
1 2 7 4 3 6

Sample Output:

2 3 -1 3 4 3

Ý tưởng

Cách làm "ngây thơ"

Cách làm dễ nhất mà các bạn đều có thể nghĩ ra là với mỗi $a_i,$ duyệt lại các giá trị $j$ từ $1$ tới $n,$ và ta có một giải thuật $O(n^2)$ . Cách làm này đương nhiên không thể phù hợp với ràng buộc của bài toán.

Cải tiến

Trước hết, ta xét một bài toán đơn giản hơn: Với mỗi $a_i,$ xác định chỉ số $j < i$ sao cho $a_j > a_i$ và $i - j$ nhỏ nhất.

Nếu như giải quyết được bài toán này trong thời gian phù hợp, thì bài toán ban đầu trở nên rất đơn giản, vì ta có thể áp dụng thêm cách làm tương tự với các $a_i$ theo chiều từ $n$ về $1,$ rồi tìm chỉ số $j > i$ thỏa mãn $a_j > a_i$ và $j - i$ nhỏ nhất.

Hãy coi dãy số $A$ giống như một dãy gồm các bạn có chiều cao $a_i,$ và người bạn thứ $i$ chỉ có thể nhìn thấy bạn thứ $j$ nếu như $j < i$ và $a_j > a_i$ . Bài toán sẽ quy về tìm chỉ số của bạn gần nhất bên trái bạn thứ $i$ sao cho bạn thứ $i$ nhìn thấy bạn đó.

Ý tưởng sẽ là "đẩy" một số bạn ra khỏi hàng, sao cho những bạn còn lại trong hàng sẽ có chiều cao giảm dần. Ta sử dụng một ngăn xếp đơn điệu để lưu chỉ số của các bạn trong hàng. Đồng thời, mỗi bạn sẽ tự ghi lại chỉ số của bạn gần nhất bên trái mình mà cao hơn mình. Xét bạn thứ $i,$ có thể xảy ra hai trường hợp:

Nếu bạn đó là người đầu hàng $(i = 1),$ thì đẩy chỉ số $i$ vào ngăn xếp và bạn đó sẽ ghi lại số $-1$ .
Nếu như thêm bạn đó vào hàng mà khiến cho ngăn xếp bị mất tính đơn điệu giảm $\big(a_i \ge a_{\text{stack.top()}}\big)$ thì ta sẽ "đẩy bớt" một số bạn đứng ở cuối hàng, cho tới khi $a_i < a_{\text{stack.top()}},$ hoặc ngăn xếp rỗng thì bạn thứ $i$ trở thành người đầu hàng. Lúc này, bạn thứ $i$ sẽ ghi lại chỉ số của bạn đứng bên cạnh mình, hoặc ghi lại $-1$ nếu như mình là người đầu hàng, đó chính là $j$ cần tìm.

Chứng minh:

Hãy giả sử có một bạn có chiều cao là $+\infty$ với chỉ số là $-1$ đứng sẵn trong hàng từ đầu. Khi đó, bạn nào đứng đầu hàng thì có thể coi như đứng ngay sau bạn này.

Xét một bạn thứ $i$ bất kỳ và đã ghi lại chỉ số $j$ . Hiển nhiên $a_j > a_i$ và $j < i$ . Giả sử có một bạn $k$ mới là người gần bạn $i$ nhất và cao hơn bạn $i$ chứ không phải bạn $j,$ thì ta có:

$\begin{cases}j < k < i. \\ a_k > a_i. \end{cases}$

Tại thời điểm bạn thứ $i$ xếp vào hàng, chắc chắn bạn thứ $k$ này đã không còn trong hàng, bởi vì nếu như vậy thì bạn thứ $i$ sẽ ghi lại chỉ số $k$ thay vì chỉ số $j$ . Tức là, bạn thứ $k$ đã bị "đẩy" khỏi hàng bởi một bạn thứ $p$ nào đó đứng sau $k$ và đứng trước $i$ . Khi đó ta có:

$\begin{cases}k < p < i. \\ a_p \ge a_k > a_i. \end{cases}$

Điều trên trái với giả thiết rằng $a_k$ là bạn gần bạn thứ $i$ nhất mà cao hơn bạn thứ $i$ . Vì vậy, điều giả sử không xảy ra, và số mà mỗi bạn ghi lại chính là chỉ số của bạn gần nhất cao hơn bạn đó (hoặc là $-1$ nếu như không ghi lại được số nào). Đây chính là chỉ số $j$ cần tìm tương ứng với $i$ .

Áp dụng vào bài toán ban đầu, ta xây dựng $l[i]$ và $r[i]$ lần lượt là chỉ số $j$ gần nhất bên trái và bên phải của $i$ sao cho $a_j > a_i,$ sau đó kết quả bài toán sẽ là $l[i]$ hoặc $r[i]$ với mỗi $i$ .

Độ phức tạp

Do mỗi phần tử sẽ đi vào hoặc đi ra khỏi ngăn xếp đúng $1$ lần, nên độ phức tạp giải thuật là $O(n)$ .

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>
#define int long long
#define task "chech_lech_nho_nhat."

using namespace std;

void enter(int &n, vector < int > &a)
{
    cin >> n;

    a.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void solution(int n, vector < int > &a)
{
    stack < int > st;

    // Xây dựng l[i] theo chiều từ trái qua phải.
    vector < int > l(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        while (!st.empty() && a[st.top()] <= a[i])
            st.pop();

        l[i] = (st.empty()) ? -1 : st.top();
        st.push(i);
    }

    // Xây dựng r[i] theo chiều từ phải qua trái.
    st = stack < int >();
    vector < int > r(n + 1);
    for (int i = n; i >= 1; --i)
    {
        while (!st.empty() && a[st.top()] <= a[i])
            st.pop();

        r[i] = (st.empty()) ? -1 : st.top();
        st.push(i);
    }

    // In kết quả.
    for (int i = 1; i <= n; ++i)
    {
        if (l[i] == -1 && r[i] == -1)
            cout << -1 << ' ';
        else
        {
            if (l[i] == -1)
                cout << r[i] << ' ';
            else if (r[i] == -1)
                cout << l[i] << ' ';
            else if (i - l[i] <= r[i] - i)
                cout << l[i] << ' ';
            else
                cout << r[i] << ' ';
        }
    }
}

main()
{
    //freopen(task"inp", "r", stdin);
    //freopen(task"out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    vector < int > a;

    enter(n, a);
    solution(n, a);

    return 0;
}

Ngôn ngữ Python:

# Nhập dữ liệu.
def enter():
    n = int(input())
    a = [0] + [int(i) for i in input().split()]

    return n, a


# Xử lý bài toán.
def solution(n, a):
    st = []

    # Tính l[i] từ bên trái qua bên phải.
    l = [0] * (n + 1)
    for i in range(1, n + 1):
        while len(st) > 0 and a[st[-1]] <= a[i]:
            st.pop()

        l[i] = -1 if len(st) == 0 else st[-1]

        st.append(i)

    # Tính r[i] từ bên phải qua bên trái.
    st.clear()
    r = [0] * (n + 1)
    for i in range(n, 0, -1):
        while len(st) > 0 and a[st[-1]] <= a[i]:
            st.pop()

        r[i] = -1 if len(st) == 0 else st[-1]

        st.append(i)

    # In kết quả.
    for i in range(1, n + 1):
        if l[i] == -1 and r[i] == -1:
            print(-1, end=' ')
        else:
            if l[i] == -1:
                print(r[i], end=' ')
            elif r[i] == -1:
                print(l[i], end=' ')
            elif i - l[i] <= r[i] - i:
                print(l[i], end=' ')
            else:
                print(r[i], end=' ')


def main():
    n, a = enter()
    solution(n, a)


if __name__ == '__main__':
    main()

3. Hình chữ nhật lớn nhất

Đề bài

Cho $n$ cột hình chữ nhật, các cột được tạo bởi những hình vuông đơn vị có độ dài cạnh bằng $1$ . Cột thứ $i$ có chiều cao là $h_i \ (1 \le i \le n)$ .

Lấy ví dụ, có $6$ cột với chiều cao lần lượt là: $[3, 6, 3, 5, 3, 2],$ thì hình chữ nhật có diện tích lớn nhất là hình tô màu vàng, diện tích là $15$ .

Hãy tìm hình chữ nhật có diện tích lớn nhất tạo thành bởi các cột?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ .
Dòng thứ hai chứa $n$ số nguyên dương $h_1, h_2, \dots, h_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

$1 \le n \le 10^5$ .
$1 \le h_i \le 10^9; \forall i: 1 \le i \le n$ .

Output:

Số nguyên duy nhất là diện tích hình chữ nhật lớn nhất tìm được.

Sample Input:

6
3 6 3 5 3 2

Sample Output:

Ý tưởng

Đầu tiên, hãy nhận xét rằng hình chữ nhật có diện tích lớn nhất luôn luôn có chiều cao bằng với chiều cao của một cột nào đó.

Với mỗi cột $i,$ gọi $l[i], r[i]$ lần lượt là chỉ số của cột gần nhất bên trái và bên phải của cột $i$ mà có chiều cao nhỏ hơn cột $i$ . Lí do làm như vậy là bởi vì, nếu giả sử hình chữ nhật kết quả có chiều cao bằng $h_i,$ thì những cột tạo thành hình chữ nhật đó cũng đều phải có chiều cao lớn hơn hoặc bằng $h_i$ .

Khi đã xác định được hai mảng $l[i], r[i]$ này thì ta sẽ duyệt qua mọi cột $i,$ giả sử rằng hình chữ nhật có diện tích lớn nhất có chiều cao là $h_i,$ rồi tính diện tích của nó bằng công thức: $\big(r[i] - l[i] - 1\big) \times h_i$ .

Việc xác định $l[i], r[i]$ theo phương pháp duyệt $O(n^2)$ thì đã quá đơn giản, nhưng tất nhiên không thể đáp ứng điều kiện thời gian. Giải pháp chính là áp dụng chính bài toán số $2,$ nhưng thay vì tìm cột cao hơn thì ta tìm cột thấp hơn cột $i$ .

Như vậy ta thu được giải thuật $O(n)$ .

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

void enter(int n, vector < int > &h)
{
    cin >> n;

    h.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
}

void solution(int n, vector < int > &h)
{
    stack < int > st;

    // Xây dựng l[i] theo chiều từ trái qua phải.
    vector < int > l(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        while (!st.empty() && h[st.top()] >= h[i])
            st.pop();

        l[i] = (st.empty()) ? 0 : st.top();
        st.push(i);
    }

    // Xây dựng r[i] theo chiều từ phải qua trái.
    st = stack < int >();
    vector < int > r(n + 1);
    for (int i = n; i >= 1; --i)
    {
        while (!st.empty() && h[st.top()] >= h[i])
            st.pop();

        r[i] = (st.empty()) ? n + 1 : st.top();
        st.push(i);
    }

    long long res = 0;
    for (int i = 1; i <= n; ++i)
        res = max(res, (r[i] - l[i] - 1) * h[i]);

    cout << res;
}

main()
{
    int n;
    vector < int > h;

    enter(n, h);
    solution(n, h);
}

Ngôn ngữ Python:

# Nhập dữ liệu.
def enter():
    n = int(input())
    h = [0] + [int(i) for i in input().split()]

    return n, h


# Xử lý bài toán.
def solution(n, h):
    st = []

    l = [0] * (n + 1)
    for i in range(1, n + 1):
        while len(st) > 0 and h[st[-1]] >= h[i]:
            st.pop()

        l[i] = 0 if len(st) == 0 else st[-1]

        st.append(i)

    st.clear()
    r = [0] * (n + 1)
    for i in range(n, 0, -1):
        while len(st) > 0 and h[st[-1]] >= h[i]:
            st.pop()

        r[i] = n + 1 if len(st) == 0 else st[-1]

        st.append(i)

    res = 0
    for i in range(1, n + 1):
        res = max(res, (r[i] - l[i] - 1) * h[i])

    print(res)


def main():
    n, h = enter()
    solution(n, h)


if __name__ == '__main__':
    main()

III. Tài liệu tham khảo

C++ stack

I. Giới thiệu chung

II. Một số bài toán minh họa

1. Số kế tiếp

Đề bài

Ý tưởng

Giải thuật ngây thơ

Cải tiến

Độ phức tạp

Cài đặt

2. Chênh lệch nhỏ nhất

Đề bài

Ý tưởng

Cách làm "ngây thơ"

Cải tiến

Độ phức tạp

Cài đặt

3. Hình chữ nhật lớn nhất

Đề bài

Ý tưởng

Cài đặt

III. Tài liệu tham khảo

Mục lục