I. Giới Thiệu Chung

Trong các chuyên đề trước, tôi đã giới thiệu cho các bạn rất chi tiết về ngăn xếp và hàng đợi, cũng như cách cài đặt và sử dụng chúng trong lập trình. Tuy nhiên, các bài tập vẫn chỉ ở mức độ rất cơ bản, chưa có tính đặc trưng của cấu trúc dữ liệu. Chuyên đề này sẽ cùng nhau khám phá về một ứng dụng cực kỳ quan trọng của ngăn xếp, đó là Ngăn Xếp Đơn Điệu.

Đúng như tên gọi, ngăn xếp đơn điệu là một ngăn xếp được cài đặt sao cho các phần tử của nó được sắp xếp thành một dãy đơn điệu, có thể là tăng hoặc giảm từ đáy tới đỉnh ngăn xếp.

Một Stack Đơn Điệu Giảm

Để cài đặt được stack đơn điệu, thông thường trước khi thêm một phần tử x vào stack, người ta thường có thao tác "lọc lại stack". Dưới đây là mã giả cho việc xây dựng một stack đơn điệu giảm:

{Chuẩn_bị_thêm_x_vào_stack}:
    while (not stack.empty()) and (stack.top() <= x):
        stack.pop();

    stack.push(x);

Bây giờ, hãy cùng đi vào phân tích một số bài toán kinh điển để hiểu rõ hơn về cách áp dụng stack đơn điệu trong lập trình thi đấu!

II. Một Số Bài Toán Minh Họa

1. Số Kế Tiếp

Đề Bài

Cho một số nguyên gồm n chữ số d1, d2,…, dn. Số kế tiếp của n là số chỉ bao gồm các chữ số d1, d2,…, dn nhưng lại lớn hơn n và là số nhỏ nhất có thể.

Hãy tìm số kế tiếp của số ban đầu?

Input:

• Dòng đầu tiên chứa số nguyên dương T - số lượng test cases.
• T nhóm dòng tiếp theo, mỗi nhóm dòng chứa một test case cấu trúc như sau:
  • Dòng đầu tiên chứa số nguyên dương n - số lượng chữ số.
  • Dòng thứ hai chứa n chữ số d1, d2,…, dn, phân cách nhau bởi dấu cách.

Ràng Buộc:

• 1≤T≤100
• 1≤n≤10^5
• 0≤di≤9; ∀i: 1≤i≤n; d1≠0

Output:

• Trên T dòng, mỗi dòng in ra một số nguyên là số kế tiếp của số đã cho trong test case tương ứng. Trong trường hợp không tìm được số kế tiếp, in ra -1.

Ví dụ Input:

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

Ví dụ Output:

15834
1474584162

Ý Tưởng Giải Thuật Ngây Thơ

Đối với n nhỏ, ta hoàn toàn có thể sử dụng quay lui để tìm tất cả các hoán vị của n chữ số, từ đó tìm ra số nhỏ nhất lớn hơn số ban đầu. Tuy nhiên, cách làm này có độ phức tạp O(n!), là rất không khả thi với số lượng lớn.

Cải Tiến Giải Thuật

Để cải tiến, ta nhận thấy rằng nếu các chữ số của số ban đầu tạo thành một dãy giảm dần từ trái qua phải, thì chắc chắn không tồn tại số kế tiếp, vì số này đã là lớn nhất. Khi đó kết quả sẽ là -1.

Ngược lại, chắc chắn việc biến đổi phải xảy ra ở một vị trí p đầu tiên tính từ bên phải mà dp<dp+1 (tức là d_p < d_{p + 1}), để số mới tạo thành là nhỏ nhất có thể nhưng vẫn lớn hơn số ban đầu. Ta có thể sử dụng ngăn xếp để tìm vị trí p này: Duyệt các vị trí i từ n về 1, thêm các chữ số d_i vào ngăn xếp sao cho tạo thành một ngăn xếp đơn điệu tăng.

Nếu như thêm chữ số d_i vào stack mà khiến cho stack bị vi phạm quy tắc đơn điệu tăng (tức là d_i >= stack.top()), thì vị trí i chính là vị trí cần thực hiện thay đổi (hay p=i).

Ta hoán đổi chữ số d_p với chữ số nhỏ nhất lớn hơn nó mà đứng sau nó.

Tới khi đó, ta đã chắc chắn tạo được một số lớn hơn số ban đầu. Tuy nhiên, ta lại mong muốn số mới thu được phải là nhỏ nhất có thể, vì vậy cần sắp xếp tăng dần các chữ số d_{p+1}...d_n.

Độ Phức Tạp

Cần phải sắp xếp lại các chữ số ở cuối, nên độ phức tạp tổng quát vẫn là O(n×log(n)).

Cài Đặt

Ngôn Ngữ C++:

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

Cài Đặt Python

def enter():
    n = int(input())
    digits = [int(i) for i in input().split()]
    return n, digits
...

2. Chênh Lệch Nhỏ Nhất

Đề Bài

Cho dãy số A gồm n số nguyên a1, a2,…, an. Với mỗi cặp số (ai, aj), ta gọi chênh lệch giữa chúng là giá trị |i−j|. Bài toán đặt ra là với mỗi ai, hãy xác định aj sao cho aj > ai và chênh lệch giữa chúng là nhỏ nhất.

Input:

• Dòng đầu tiên chứa số nguyên dương n - số lượng phần tử của dãy số.
• Dòng thứ hai chứa n số nguyên a1, a2,…, an, phân cách nhau bởi dấu cách.

Ràng Buộc:

• 1≤n≤10^6
• 1≤ai≤10^9; ∀i: 1≤i≤n

Output:

• Ứng với mỗi ai, đưa ra chỉ số j của phần tử aj tìm được. Nếu không tìm được, thì đưa ra -1.

Ý Tưởng Giải Thuật Ngây Thơ

Cách làm dễ nhất mà các bạn đều có thể nghĩ ra là với mỗi ai, duyệt lại các giá trị j từ 1 tới n, và ta có một giải thuật O(n^2), đương nhiên không thể phù hợp với ràng buộc của bài toán.

Cải Tiến Giải Thuật

Ta sẽ xây dựng giải thuật để tìm chỉ số gần nhất bên trái và bên phải cho mỗi ai sao cho aj > ai. Bằng cách sử dụng ngăn xếp, ta sẽ duy trì các chỉ số của các phần tử trong dãy sao cho chúng có chiều cao giảm dần.

Bằng cách duyệt từ trái qua phải và phải qua trái, ta có thể nhanh chóng tìm được vị trí cần thiết cho mọi phần tử và từ đó cho ra kết quả thỏa mãn yêu cầu.

Độ Phức Tạp

Độ phức tạp giải thuật này là O(n), rất hiệu quả cho kích thước lớn.

Cà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)
...

Ngôn Ngữ Python:

def enter():
...

3. Hình Chữ Nhật Lớn Nhất

Đề Bài

Cho n cột hình chữ nhật, các cột được tạo bởi những hình vuông đơn vị có độ dài cạnh bằng 1. Cột thứ i có chiều cao là hi. Hãy tìm hình chữ nhật có diện tích lớn nhất được tạo thành bởi các cột này.

Cài Đặt

Ta sử dụng kỹ thuật ngăn xếp để giải quyết bài toán tối ưu một cách nhanh chóng. Bằng cách lưu giữ vị trí của các cột phù hợp, ta có thể tính được diện tích của hình chữ nhật cho mỗi cột trong quá trình duyệt.

Độ Phức Tạp

Độ phức tạp của giải thuật cũng là O(n), đảm bảo hiệu suất cho đầu vào lớn.

Tham Khảo

• Tài liệu về ngăn xếp
• Một số bài toán tương tự
  source: viblo