Chứng khoán trực tuyến (Online Stock Span) trong C++

Thiết kế lớp StockSpanner với phương thức next(price) trả về "span" của giá hôm nay: số ngày liên tiếp trước đó (kể cả hôm nay) mà giá ≤ giá hôm nay.

Ví dụ: [100, 80, 60, 70, 60, 75, 85] → span [1, 1, 1, 2, 1, 4, 6].

Thuật toán giải quyết (Stack đơn điệu giảm dần)

Stack lưu cặp (price, span) với giá giảm dần. Khi giá mới đến, pop các giá ≤ giá mới và cộng dồn span.

1. Khởi tạo stack rỗng.
2. next(price):
   • span = 1.
   • Trong khi stack không rỗng và stack.top().price <= price: span += stack.top().span, pop.
   • Push (price, span).
   • Trả về span.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class StockSpanner {
    vector<pair<int, int>> st; // {price, span}
public:
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.back().first <= price) {
            span += st.back().second;
            st.pop_back();
        }
        st.push_back({price, span});
        return span;
    }
};

int main() {
    StockSpanner ob;
    cout << ob.next(100) << endl;
    cout << ob.next(80) << endl;
    cout << ob.next(60) << endl;
    cout << ob.next(70) << endl;
    cout << ob.next(60) << endl;
    cout << ob.next(75) << endl;
    cout << ob.next(85) << endl;
}

Đầu vào

Initialize the class, then call next() method using different values. See the main() method

Đầu ra

1 1 1 2 1 4 6