Stack đơn điệu là cấu trúc dữ liệu đặc biệt trong đó các phần tử được sắp xếp theo thứ tự không giảm hoặc không tăng. Có hai dạng chính:

• Stack tăng dần: từ đáy đến đỉnh, giá trị giảm dần
• Stack giảm dần: từ đáy đến đỉnh, giá trị tăng dần

Cơ chế hoạt động

Xét dãy số: 10, 3, 7, 4, 12 với stack tăng dần:

1. 10: Stack rỗng → push → Stack: [10]
2. 3: 3 < 10 (đỉnh) → push → Stack: [10, 3]
3. 7: 7 > 3 (đỉnh) → pop 3; 7 < 10 → push → Stack: [10, 7]
4. 4: 4 < 7 → push → Stack: [10, 7, 4]
5. 12: 12 > 4 → pop 4; 12 > 7 → pop 7; 12 > 10 → pop 10; Stack rỗng → push → Stack: [12]

Mẫu thuật toán

stack<int> stk;
// Thêm phần tử kết thúc để xử lý hết stack
for (duyệt mảng) {
    if (stk.empty() || giá_trị[stk.top()] >= giá_trị_hiện_tại) {
        stk.push(chỉ_số);
    } else {
        while (!stk.empty() && giá_trị[stk.top()] < giá_trị_hiện_tại) {
            int idx = stk.top(); stk.pop();
            cập_nhật_kết_quả(idx, chỉ_số_hiện_tại);
        }
        stk.push(chỉ_số_hiện_tại);
    }
}

Bài toán 1: Tổng tầm nhìn

Mô tả: n người đứng thành hàng, mỗi người nhìn sang phải. Người cao hơn nhìn thấy tóc người thấp hơn. Tính tổng số kiểu tóc nhìn thấy được.

Input: [4, 3, 7, 1] → Output: 2

Giải thích: Người cao 4 nhìn thấy người cao 3; người cao 7 nhìn thấy người cao 1.

int visionSum(vector<int>& heights) {
    heights.push_back(INT_MAX); // Người "vô cực" ở cuối
    stack<int> pos;
    int total = 0;
    
    for (int i = 0; i < heights.size(); i++) {
        if (pos.empty() || heights[pos.top()] > heights[i]) {
            pos.push(i);
        } else {
            while (!pos.empty() && heights[pos.top()] <= heights[i]) {
                int cur = pos.top(); pos.pop();
                total += (i - cur - 1); // Số người bị che giữa
            }
            pos.push(i);
        }
    }
    return total;
}

Bài toán 2: Hình chữ nhật lớn nhất trong biểu đồ cột

Tìm diện tích hình chữ nhật lớn nhất có thể tạo từ các cột liên tiếp.

int maxRectangle(vector<int>& bars) {
    bars.push_back(-1); // Cột "âm vô cực" để xả hết stack
    stack<int> idx;
    int best = 0;
    
    for (int i = 0; i < bars.size(); i++) {
        if (idx.empty() || bars[idx.top()] <= bars[i]) {
            idx.push(i);
        } else {
            int leftmost;
            while (!idx.empty() && bars[idx.top()] > bars[i]) {
                int h = bars[idx.top()]; idx.pop();
                int w = idx.empty() ? i : i - idx.top() - 1;
                best = max(best, h * w);
                leftmost = h; // Lưu vị trí trái nhất có thể mở rộng
            }
            idx.push(leftmost);
            bars[leftmost] = bars[i]; // Gán lại để mở rộng trái sau này
        }
    }
    return best;
}

Kỹ thuật mở rộng: Khi gặp cột thấp hơn, ta không chỉ tính diện tích mà còn "kéo dài" vị trí của cột cao về trái nhất có thể. Điều này cho phép các cột sau mở rộng sang trái qua vùng đã pop.

Bài toán 3: Tích cực đại của tổng và min

Mô tả: Tìm đoạn con liên tiếp sao cho (tổng các phần tử) × (giá trị nhỏ nhất) đạt cực đại.

struct Result {
    long long value;
    int left, right;
};

Result maxSubarrayProduct(vector<int>& arr) {
    int n = arr.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    
    arr.push_back(-1); // Sentinel
    stack<int> st;
    Result ans = {0, 0, 0};
    
    for (int i = 0; i <= n; i++) {
        if (st.empty() || arr[st.top()] <= arr[i]) {
            st.push(i);
        } else {
            int boundary;
            while (!st.empty() && arr[st.top()] > arr[i]) {
                int pos = st.top(); st.pop();
                long long sum = prefix[i] - prefix[pos];
                long long prod = sum * arr[pos];
                if (prod > ans.value) {
                    ans = {prod, pos + 1, i}; // [pos+1, i-1] trong gốc
                }
                boundary = pos;
            }
            st.push(boundary);
            arr[boundary] = arr[i]; // Kế thừa vị trí trái nhất
        }
    }
    return ans;
}

Phân tích độ phức tạp

Mỗi phần tử chỉ vào stack một lần và ra một lần → O(n) thời gian, O(n) không gian phụ.