Ngăn xếp đơn điệu: tìm phần tử lớn hơn và hình chữ nhật lớn nhất

Từ bài tìm số lớn hơn gần nhất đến Stack

Cho mảng [2, 1, 5, 6, 2, 3]. Với mỗi phần tử, tìm giá trị đầu tiên lớn hơn nó ở bên phải; nếu không có, ghi -1. Kết quả là [5, 5, 6, -1, 3, -1]. Chú ý “gần nhất” là gần theo vị trí, không phải số nhỏ nhất trong mọi giá trị lớn hơn nó. Với số 2 đầu mảng, chọn 5 vì gặp 5 trước 6.

Cách trực tiếp duyệt từ mỗi vị trí sang phải có thể xét khoảng n² cặp. Thay vì tìm riêng từng phần tử, ta đọc mảng một lần và để những phần tử chưa có đáp án chờ trên ngăn xếp. Khi một số mới xuất hiện, nó có thể giải đáp cho nhiều phần tử đang chờ cùng lúc.

Bất biến của ngăn xếp giảm

Stack chứa các chỉ số có giá trị không tăng từ đáy tới đỉnh. Đọc a[i], nếu giá trị ở đỉnh nhỏ hơn a[i], lấy chỉ số đó ra và gán đáp án bằng a[i]. Tiếp tục đến khi stack rỗng hoặc đỉnh không nhỏ hơn số mới. Cuối lượt đưa chỉ số i vào chờ.

Vì sao số mới chính là số lớn hơn gần nhất cho phần tử vừa lấy? Phần tử đó đã chờ từ trước mà chưa gặp số đủ lớn; nếu có số đủ lớn nằm giữa, nó đã được giải đáp ở lượt trước. Vì thế thời điểm lấy ra đầu tiên cho đúng vị trí gần nhất bên phải. Đây là lý do dùng thứ tự duyệt từ trái qua phải và xử lý mọi phần tử bị vượt qua ngay khi đọc số mới.

Các vị trí còn chờ khi hết mảng không có đáp án, nên giữ -1. Nếu cần phân biệt một giá trị -1 thật với trạng thái không tồn tại, lưu chỉ số kết quả hoặc dùng thêm cờ; không nên chọn một giá trị báo lỗi có thể lẫn với dữ liệu.

Code C++ và Python: hai ứng dụng

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> lon_hon_ben_phai(const vector<int>& a) {
    vector<int> st, ans(a.size(), -1);
    for (int i=0; i<(int)a.size(); ++i) {
        while (!st.empty() && a[st.back()] < a[i]) {
            ans[st.back()] = a[i]; st.pop_back();
        }
        st.push_back(i);
    }
    return ans;
}
// Chiều cao không âm, diện tích vừa long long.
long long chu_nhat_lon_nhat(const vector<int>& h) {
    vector<int> st; long long best=0;
    for (int i=0; i<=(int)h.size(); ++i) {
        int cur = i==(int)h.size() ? 0 : h[i];
        while (!st.empty() && h[st.back()] > cur) {
            int height=h[st.back()]; st.pop_back();
            int left=st.empty() ? -1 : st.back();
            best=max(best,1LL*height*(i-left-1));
        }
        if (i<(int)h.size()) st.push_back(i);
    }
    return best;
}
int main() {
    int n; vector<int> a={2,1,5,6,2,3};
    if(cin>>n) {a.resize(n);for(int& x:a)cin>>x;}
    for(int x:lon_hon_ben_phai(a))cout<<x<<' ';
    cout<<'\n'<<chu_nhat_lon_nhat(a)<<'\n';
}

def lon_hon_ben_phai(a):
    st, ans = [], [-1] * len(a)
    for i, x in enumerate(a):
        while st and a[st[-1]] < x:
            ans[st.pop()] = x
        st.append(i)
    return ans

def chu_nhat_lon_nhat(h):
    st, best = [], 0
    for i in range(len(h) + 1):
        cur = 0 if i == len(h) else h[i]
        while st and h[st[-1]] > cur:
            height = h[st.pop()]
            left = st[-1] if st else -1
            best = max(best, height * (i - left - 1))
        if i < len(h):
            st.append(i)
    return best

if __name__ == '__main__':
    import sys
    d = list(map(int, sys.stdin.read().split()))
    a = d[1:1+d[0]] if d else [2,1,5,6,2,3]
    print(*lon_hon_ben_phai(a))
    print(chu_nhat_lon_nhat(a))

Tệp ví dụ in hai dòng: 5 5 6 -1 3 -1 cho bài tìm số lớn hơn bên phải, rồi 10 cho bài hình chữ nhật ở phần tiếp theo. Khi tự nhập dữ liệu, dòng đầu là n không âm, sau đó là n chiều cao không âm. Các hàm không sửa mảng đầu vào. Để tự kiểm tra trên các mảng nhỏ, bạn nên viết thêm hàm hai vòng lặp vét cạn để đối chiếu kết quả ở các dãy tăng dần, giảm dần và có chiều cao bằng 0.

Trong C++, vector lưu chỉ số và dùng back() làm đỉnh. Trong Python, list với append và pop đóng vai trò tương tự. Bản thân thao tác thêm vào mảng động có chi phí khấu hao; tổng số lần thêm/xóa của thuật toán vẫn tuyến tính. Không dùng xóa ở đầu list để thay pop cuối.

Vì sao không phải O(n²)?

Đúng là có vòng while bên trong vòng for. Nhưng đừng nhân hai cận n một cách máy móc. Mỗi chỉ số được đẩy lên đúng một lần. Sau khi bị lấy ra, chỉ số đó không quay lại stack. Trên toàn bộ chương trình có n lần đẩy và tối đa n lần lấy, nên tổng thời gian là O(n), bộ nhớ phụ O(n).

Một lượt có thể lấy ra rất nhiều phần tử, ví dụ đọc số 100 sau dãy giảm dài. Chi phí lớn của lượt đó dùng các phần tử đã tích lũy từ trước; các lượt khác không thể lấy lại chúng. Đây là phân tích tổng số thao tác, không phải lời khẳng định mỗi lượt riêng lẻ luôn O(1).

Hình chữ nhật lớn nhất trong biểu đồ cột

Với chiều cao [2, 1, 5, 6, 2, 3], hình chữ nhật cao 5 trên hai cột có chiều cao 5 và 6 cho diện tích 10. Ta cần tìm diện tích lớn nhất của một vùng gồm các cột liên tiếp. Chiều cao vùng là giá trị nhỏ nhất trong vùng, vì hình chữ nhật phải nằm dưới mọi cột.

Lần này stack giữ các chỉ số có chiều cao không giảm. Khi gặp một cột thấp hơn đỉnh, cột ở đỉnh không thể mở rộng qua vị trí hiện tại. Lấy nó ra, đặt chiều cao bằng giá trị của cột đó. Nếu chỉ số hiện tại là i và đỉnh còn lại sau khi lấy là left, bề rộng có thể dùng là i - left - 1. Nếu stack rỗng thì coi left bằng -1.

Ví dụ ở i = 4 có chiều cao 2: lấy cột 6 ra trước, bề rộng 1, diện tích 6. Tiếp tục lấy cột 5, bên trái còn cột cao 1 ở chỉ số 1, nên bề rộng là 4 - 1 - 1 = 2, diện tích 10. Cuối mảng dùng một lượt chiều cao 0 để xử lý các cột còn chờ. Mỗi cột vẫn chỉ thêm/xóa tối đa một lần.

Phần tử bằng nhau và biến thể trái/phải

Trong Next Greater Element, code dùng <: phần tử bằng nhau chưa đủ làm đáp án. Nếu đổi sang <=, bạn đang tìm lớn hơn hoặc bằng. Với [2, 2], hai yêu cầu này cho kết quả khác nhau nên đây là ca kiểm bắt buộc.

Code histogram cũng dùng dấu > khi lấy cột; các cột bằng nhau được giữ lại và lần lượt tính các bề rộng. Có thể thiết kế bản lấy cả phần tử bằng nhau, nhưng cách xác định biên phải được giữ nhất quán. Với bài tính tổng cực tiểu mọi đoạn, cách chia quyền sở hữu giữa các giá trị bằng nhau còn ảnh hưởng đếm trùng, nên không chép nguyên dấu so sánh từ bài khác.

Muốn tìm phần tử gần nhất bên trái, bạn có thể đổi hướng duyệt hoặc đổi thời điểm đọc đáp án ở đỉnh. Trước khi viết, hãy chốt ba câu: cần phía nào, cần lớn/nhỏ thế nào, và phần tử bằng nhau có được chấp nhận không.

Luyện ngay trên Big-O Coding

Hai bài hồ bơi và biểu đồ cột luyện giới hạn chiều cao của hình chữ nhật. Bài tổng cực tiểu là bước nâng cao, cần xử lý rõ các giá trị bằng nhau để mỗi đoạn chỉ tính một lần.

Câu hỏi thường gặp

Nguồn tham khảo

• cp-algorithms: Minimum stack / minimum queue
• USACO Guide: Stacks
• cppreference: std::vector