คำอธิบายปัญหา
กำหนดลิสต์ nums หาผลรวมของค่าต่ำสุด (minimum) ของทุก sublist ที่เป็นไปได้ หากผลลัพธ์ใหญ่เกิน ให้ modulo 10^9 + 7
ตัวอย่าง
nums = [5, 10, 20, 10, 0] → Output: 90
Sublists ทั้งหมด 15 ชุด ค่าต่ำสุดแต่ละชุด: [5, 10, 20, 10, 0, 5, 10, 10, 0, 5, 10, 0, 5, 0, 0] ผลรวม = 90
ขั้นตอนการแก้ปัญหา (Monotonic Stack)
- ใช้ stack เก็บ
[index, value, contribution]โดยcontribution= จำนวน subarray ที่จบที่ index นี้ และมีค่านี้เป็น minimum - วนลูปแต่ละ element:
- Pop stack ขณะค่าปัจจุบัน ≤ ค่าบนสุด stack (ลบ contribution เก่าออก)
- คำนวณ contribution ใหม่: หาก stack ว่าง →
(i+1)*valไม่ว่าง →(i - stack[-1][0])*val - Push เข้า stack, อัปเดต
temp_sumและans
การตนการทำงาน (Python)
def solve(nums):
ans = 0
s = []
temp_sum = 0
for index, value in enumerate(nums):
while s and value <= s[-1][1]:
temp_sum -= s[-1][2]
s.pop()
if not s:
s.append([index, value, (index + 1) * value])
else:
s.append([index, value, (index - s[-1][0]) * value])
temp_sum += s[-1][2]
ans += temp_sum
return ans % (10**9 + 7)
nums = [5, 10, 20, 10, 0]
print(solve(nums)) # Output: 90
อินพุต / เอาต์พุต
Input: [5, 10, 20, 10, 0] Output: 90
