สมมติว่าเรามีอาเรย์ A ของจำนวนเต็ม เราต้องหาจำนวน subarray ที่ต่อเนื่องและไม่ว่าง ที่เงื่อนไข: องค์ประกอบซ้ายสุดของ subarray ไม่ใหญ่กว่าองค์ประกอบอื่นๆ ใน subarray นั้น
ดังนั้น หากอินพุทคือ [1,4,2,5,3] ผลลัพธ์จะเป็น 11 เนื่องจากมี valid subarrays 11 ตัว คือ [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
ret := 0
n := ขนาดของ nums
กำหนด stack st
for i := 0 ถึงขนาดของ nums - 1:
x := nums[i]
while (st ไม่ว่าง และ x < โหนดบนสุดของ st): ลบองค์ประกอบออกจาก st
ใส่ x ลง st
ret := ขนาดของ st + ret
คืนค่า ret
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int validSubarrays(vector& nums) {
int ret = 0;
int n = nums.size();
stack st;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
while (!st.empty() && x < st.top()) st.pop();
st.push(x);
ret += st.size();
}
return ret;
}
};
int main() {
Solution ob;
vector v = {1, 4, 2, 5, 3};
cout << (ob.validSubarrays(v));
return 0;
}
อินพุต
{1,4,2,5,3}
เอาต์พุต
11
