Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में वैलिड सबऐरे की संख्या

मान लीजिए हमारे पास पूर्णांकों का एक ऐरे 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
  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस

  1. C++ में वैलिड सुडोकू C++ में वैलिड सुडोकू

    मान लीजिए हमें 9×9 मैट्रिक्स दिया गया है जिसे सुडोकू कहा जाता है। कार्य यह जांचना है कि दिया गया सुडोकू पैटर्न मान्य है या नहीं। सामान्य तौर पर, एक सुडोकू बोर्ड इस तरह दिखता है, सुडोकू के नियम - हर रो में 1-9 की रेंज में एक नंबर होता है हर कॉलम में 1-9 की रेंज में नंबर होते हैं। 3×3 का प्रत्येक ब्