Trong quá trình xây dựng các ứng dụng web phía client bằng JavaScript, làm thế nào để sử dụng cấu trúc dữ liệu Stack nhằm triển khai thuật toán tìm kiếm phần tử nhỏ hơn trước đó (Previous Smaller Element) cho một mảng dữ liệu giá sản phẩm, giúp tối ưu hóa hiệu năng xử lý so với thuật toán duyệt mảng lồng nhau thông thường?

Question

Accepted Answer

Bản chất vấn đề và ngữ cảnh thực tế
Trong các ứng dụng thương mại điện tử cấp độ doanh nghiệp, việc phân tích dữ liệu biến động giá sản phẩm theo thời gian thực (như tìm kiếm mức giá thấp hơn gần nhất so với thời điểm hiện tại cho từng mốc thời gian) là một bài toán phổ biến. Nếu sử dụng cách tiếp cận duyệt mảng lồng nhau (Nested Loops), độ phức tạp thời gian sẽ là O(n^2), gây nghẽn cổ chai hiệu năng (Performance Bottleneck) khi kích thước mảng dữ liệu lớn.
Sử dụng cấu trúc dữ liệu Stack (nguyên lý LIFO - Last In, First Out) giúp giải quyết bài toán này với độ phức tạp thời gian tối ưu tuyến tính O(n).
Thuật toán chi tiết sử dụng Stack

Khởi tạo một Stack rỗng để lưu trữ các chỉ số (indices) hoặc giá trị của mảng.
Khởi tạo một mảng kết quả với kích thước tương đương mảng đầu vào.
Duyệt qua từng phần tử của mảng từ trái sang phải:
Trong khi Stack không rỗng và phần tử đỉnh của Stack lớn hơn hoặc bằng phần tử hiện tại, tiến hành loại bỏ (pop) phần tử khỏi Stack.
Nếu Stack trở thành rỗng, nghĩa là không có phần tử nào nhỏ hơn ở phía trước, gán giá trị mặc định (ví dụ: -1).
Nếu Stack không rỗng, phần tử ở đỉnh Stack chính là phần tử nhỏ hơn gần nhất nằm bên trái.
Đưa phần tử hiện tại vào (push) Stack để tiếp tục phục vụ cho các vòng lặp sau.

Ví dụ mã nguồn minh họa (JavaScript)
function findPreviousSmallerElements(prices) {
    const n = prices.length;
    const result = new Array(n);
    const stack = [];

for (let i = 0; i < n; i++) {
        // Loại bỏ các phần tử lớn hơn hoặc bằng giá trị hiện tại
        while (stack.length > 0 && stack[stack.length - 1] >= prices[i]) {
            stack.pop();
        }

// Nếu Stack rỗng, không có phần tử nhỏ hơn ở bên trái
        if (stack.length === 0) {
            result[i] = -1;
        } else {
            // Phần tử đỉnh Stack là phần tử nhỏ hơn gần nhất
            result[i] = stack[stack.length - 1];
        }

// Đẩy giá trị hiện tại vào Stack
        stack.push(prices[i]);
    }

return result;
}

// Kiểm thử thực tế
const inputPrices = [4, 5, 2, 10, 8];
console.log(findPreviousSmallerElements(inputPrices)); 
// Kết quả: [-1, 4, -1, 2, 2]
Lưu ý kinh nghiệm thực chiến dành cho Lập trình viên Junior

Độ phức tạp không gian (Space Complexity): Thuật toán này sử dụng thêm một Stack và một mảng kết quả, do đó độ phức tạp không gian là O(n). Cần cân nhắc giải phóng bộ nhớ khi xử lý các tập dữ liệu lớn trên client-side để tránh rò rỉ bộ nhớ (Memory Leak).
Ứng dụng thực tế: Kỹ thuật Monotonic Stack (Stack đơn điệu) này thường được áp dụng trong các biểu đồ tài chính, tối ưu hóa truy vấn dữ liệu DOM ảo (Virtual DOM), hoặc phân tích cú pháp trong các hệ thống doanh nghiệp.

Bản chất vấn đề và ngữ cảnh thực tế

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi stacks liên quan cùng chủ đề