[STLC++Stack] stickSpan

Đề bài

Cho chiều cao của các thanh gỗ theo thứ tự từ trái qua phải, ứng với mỗi thanh gỗ bạn gần phải xác định khoảng cách tới thanh gỗ nằm bên trái và dài hơn nó là bao nhiêu.

Ví dụ

Chiều cao các thanh gỗ là arr = [100,80,60,70,60,75,85]

Output sẽ có dạng stickSpan[arr] = [1,1,1,2,1,4,6]

Hướng dẫn:

Khởi tạo stack st dùng để lưu các chỉ số của dãy arr, phải đảm bảo rằng arr[st[k] > arr[st[k+1], khởi tạo st chỉ có 1 số 0.

Duyệt từ 1 đến n:

• Tìm chỉ số k lớn nhất sao cho arr[k] > arr[i]. Tìm số k bằng cách duyệt stack, nếu st.top() nhỏ hơn thì ta xóa chỉ số đó.
• Nếu xóa sạch st thì khoảng cách từ arr[i] đến thành gỗ bên trái nó là i+1 còn không sẽ là i - st.top().
• Thêm i và st.

std::vector<int> stickSpan(std::vector<int> arr)
{
    stack<int> st;
    vector < int > res;
    int n = arr.size();
    st.push(0); 
    res.push_back(1);

    for (int i = 1; i < n; i++) {
        while (!st.empty() && arr[st.top()] <= arr[i]) 
            st.pop(); 
        res.push_back((st.empty()) ? (i + 1) : (i - st.top())); 
        st.push(i); 
    }

    return res;
}