[STLC++Stack] popMin

Bài tập.

Cho một danh sách các số nguyên dương arr dưới dạng vector<int>. Bạn cần phải đưa từng phần tử trong danh sách này vào stack. Sau đó output giá trị nhỏ nhất trong stack trước mỗi lần pop(). Xem ví dụ để hiểu rõ hơn.

Ví dụ

• Với arr = [4,2,6,7,8,1] thìpopMin(arr) = [1,2,2,2,2,4]
Giải thích: từ arr có được stack: [4,2,6,7,8,1] với 1 là top. Trước khi pop() thì 1 là giá trị nhỏ nhất và sau khi pop() stack trở thành [4,2,6,7,8] và 2 là giá trị nhỏ nhất, cứ thế ta có kết quả [1,2,2,2,2,4].

Hướng dẫn.

Hãy chú ý là thứ tự các phần tự trong kết quả và stack st_min sẽ ngược nhau. Nên bài toán được hiểu như sau sẽ đơn gian hơn: tạo một vector v với v[i] là phần tử nhỏ nhất từ vị trí 0 đến vị trí i. Sau đó in ngược vector v ra. Để tránh phải in ngược ta dùng luôn một stack st_min để lưu thay thế cho vector v.

Code mẫu:

std::vector<int> popMin(std::vector<int> arr)
{
    stack<int> st_min;
    vector<int> res;
    st_min.push(arr[0]);
    for(int i=1; i<arr.size(); i++){
        if(arr[i]>=st_min.top())st_min.push(st_min.top());
        else st_min.push(arr[i]);
    }
    while(st_min.empty() == false){
        res.push_back(st_min.top());
        st_min.pop();
    }
    return res;
}