मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है, हमें गैर-खाली निरंतर सबऐरे की संख्या ज्ञात करनी है जो इस शर्त को पूरा करते हैं: सबऐरे का बायां एलिमेंट सबऐरे के अन्य एलिमेंट्स से बड़ा नहीं है।
तो, यदि इनपुट [1,4,2,5,3] है, तो आउटपुट 11 होगा, क्योंकि 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 का आकार
एक स्टैक st परिभाषित करें
i := 0 से शुरू करें, जब i < nums का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
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& 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));
}
इनपुट
{1,4,2,5,3}
आउटपुट
11