Online Stock Span ใน C++: คำนวณ Stock Span แบบ Real-time

โจทย์

ออกแบบ class StockSpanner รองรับ next(price) คืน "span" = จำนวนวันติดต่อกันย้อนหลัง (รวมวันนี้) ที่ราคา ≤ ราคาวันนี้

ตัวอย่าง: [100,80,60,70,60,75,85] → [1,1,1,2,1,4,6]

แนวคิด: Monotonic Stack (Decreasing)

เก็บคู่ (price, span) ใน stack เรียงราคาลดลง
วันใหม่: pop ทั้งหมดที่ ≤ price รวม span เข้าไป แล้ว push ใหม่

ขั้นตอน

1. Stack เก็บ pair<int, int> = {price, span}
2. next(price):
   • span = 1
   • while !st.empty() && st.top().first <= price:
     • span += st.top().second
     • st.pop()
   • st.push({price, span})
   • return span

ตัวอย่างโค้ด C++

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

class StockSpanner {
    stack<pair<int, int>> st; // {price, span}
public:
    StockSpanner() {}
    
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        st.push({price, span});
        return span;
    }
};

int main() {
    StockSpanner ob;
    cout << ob.next(100) << " "; // 1
    cout << ob.next(80) << " ";  // 1
    cout << ob.next(60) << " ";  // 1
    cout << ob.next(70) << " ";  // 2
    cout << ob.next(60) << " ";  // 1
    cout << ob.next(75) << " ";  // 4
    cout << ob.next(85) << " ";  // 6
    return 0;
}

อินพุต / เอาต์พุต

Input: เรียก next() ตามลำดับ: 100, 80, 60, 70, 60, 75, 85

Output: 1 1 1 2 1 4 6

ความซับซ้อน

• Time: Amortized O(1) ต่อการเรียก (แต่ละราคา push/pop สูงสุด 1 ครั้ง)
• Space: O(n) - stack