সি++-এ বৈধ সাবঅ্যারের সংখ্যা

ধরা যাক A হল একটি পূর্ণসংখ্যা অ্যারে, আমাদের নন-এমপ্টি কন্টিনিউয়াস সাবঅ্যারে সংখ্যা খুঁজে বের করতে হবে যা এই শর্ত পূরণ করে: সাবঅ্যারেতি বামপাশের উপাদানটি সাবঅ্যারেতি অন্য উপাদানগুলোর চেয়ে বড় নয়।

তাই, যদি ইনপুট [1,4,2,5,3] হয়, তবে আউটপুট হবে ১১, কারণ ১১টি বৈধ সাবঅ্যারে আছে, সেগুলো হল [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-এর আকার
একটি স্ট্যাক st ডিফাইন করুন
i := 0 থেকে শুরু করুন, যখন i < nums-এর আকার, (i ১ করে বাড়ান), করুন -
- x := nums[i]
- যখন (st খালি নয় এবং x < st-এর টপ এলিমেন্ট), করুন -
  - st-থেকে এলিমেন্ট ডিলিট করুন
- x st-এ ইনসার্ট করুন
- ret := st-এর আকার + ret
ret রিটার্ন করুন

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন -

উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int validSubarrays(vector<int>& nums) {       int ret = 0;       int n = nums.size();       stack <int> 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;    } }; main(){    Solution ob;    vector<int> v = {1,4,2,5,3};    cout << (ob.validSubarrays(v)); }

ইনপুট

{1,4,2,5,3}