สมมติว่าเรามี API ที่รวบรวมราคารายวันสำหรับหุ้นบางตัว และส่งคืนช่วงราคาหุ้นนั้นสำหรับวันปัจจุบัน ขอบเขตของราคาหุ้นวันนี้ถูกกำหนดเป็น −
- จำนวนวันต่อเนื่องสูงสุด (เริ่มตั้งแต่วันนี้และย้อนกลับ) โดยที่ราคาหุ้นน้อยกว่าหรือเท่ากับราคาวันนี้
ตัวอย่างเช่น หากเราเห็นบันทึกการแชร์หุ้น 7 วัน เช่น [100, 80, 60, 70, 60, 75, 85] จากนั้นช่วงสต็อกจะเป็น [1, 1, 1, 2, 1, 4, 6] เราต้องเขียนโมดูลจริงสำหรับ API นั้น ซึ่งจะใช้เมื่อโมดูลนี้ถูกเรียก
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดสองอาร์เรย์ st, v และตัวนับ ตั้งค่าตัวนับเป็น 0
- เพิ่มตัวนับ 1
- ในขณะที่ st ไม่ว่างเปล่าและราคา>=v[stack top element]
- ป๊อปจากสแต็ก
- ans :=ตัวนับเมื่อ stack ว่างเปล่า มิฉะนั้น ans :=counter – stack top
- ใส่ราคาใน v
- ใส่ตัวนับเข้า st
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class StockSpanner {
public:
vector <int> st;
int counter;
vector <int> v;
StockSpanner() {
counter = 0;
}
int next(int price) {
counter++;
while(!st.empty() && price >= v[st.back() - 1])st.pop_back();
int ans = st.empty() ? counter : counter - st.back();
v.push_back(price);
st.push_back(counter);
return ans ;
}
};
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;
} อินพุต
Initialize the class, then call next() method using different values. See the main() method
ผลลัพธ์
1 1 1 2 1 4 6
