mcq - what is algorithm in english




हिस्टोग्राम के नीचे आयताकार क्षेत्र को अधिकतम करें (6)

आप हे (एन) विधि का उपयोग कर सकते हैं जो हिस्टोग्राम के तहत अधिकतम क्षेत्र की गणना करने के लिए स्टैक का उपयोग करता है।

long long histogramArea(vector<int> &histo){
   stack<int> s;
   long long maxArea=0;
   long long area= 0;
   int i =0;
   for (i = 0; i < histo.size();) {
    if(s.empty() || histo[s.top()] <= histo[i]){
        s.push(i++);
    }
    else{
        int top = s.top(); s.pop();
        area= histo[top]* (s.empty()?i:i-s.top()-1);
        if(area >maxArea)
            maxArea= area;
    }
  }
  while(!s.empty()){
    int top = s.top();s.pop();
    area= histo[top]* (s.empty()?i:i-s.top()-1);
    if(area >maxArea)
        maxArea= area;
 }
 return maxArea;
}

स्पष्टीकरण के लिए आप यहां पढ़ सकते हैं http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

मेरे पास पूर्णांक हाइट्स और स्थिर चौड़ाई वाला हिस्टोग्राम है I। हिस्टोग्राम के नीचे आयताकार क्षेत्र को अधिकतम करना चाहता हूं I उदाहरण के लिए:

 _
| |
| |_ 
|   |
|   |_
|     |

इसके लिए जवाब 6, 3 * 2 होगा, कॉल 1 और कॉल 2 का उपयोग कर।

हे (एन ^ 2) ब्रूट बल मेरे लिए स्पष्ट है, मैं एक ओ (एन लॉग एन) एल्गोरिथ्म चाहूंगा मैं अधिकतम वृद्धि के बाद वाले ओ (एन लॉग एन) एल्गो की तर्ज पर गतिशील प्रोग्रामिंग सोचने की कोशिश कर रहा हूं, लेकिन आगे नहीं जा रहा हूं। क्या मुझे विभाजन और एल्गोरिदम को जीतना चाहिए?

पीएस: अगर कोई ऐसा समाधान नहीं है तो पर्याप्त प्रतिष्ठा वाले लोगों को विभाजित और जीतने वाले टैग को हटाने का अनुरोध किया जाता है

चू के टिप्पणियों के बाद: मेरा मतलब है कि सबसे बड़ा आयताकार क्षेत्रफल पूरी तरह से फिट बैठता है। (स्पष्टीकरण के लिए धन्यवाद j_random_hacker :))।


ऊपर दिए गए उत्तरों ने कोड में सबसे अच्छा ओ (एन) समाधान दिया है, हालांकि, उनकी व्याख्या समझने में काफी मुश्किल है। एक स्टैक का इस्तेमाल करते हुए ओ (एन) एल्गोरिथ्म मुझे पहले जादू लग रहा था, लेकिन अभी यह मेरे लिए हर भावना बनाता है ठीक है, मुझे इसकी व्याख्या करें।

पहला अवलोकन:

अधिकतम आयत को खोजने के लिए, यदि हर बार x , हम अपने प्रत्येक तरफ पहले छोटी बार जानते हैं, हम कहते हैं कि l और r , हम निश्चित हैं कि height[x] * (r - l - 1) सबसे अच्छा शॉट है बार x की ऊंचाई का उपयोग करके प्राप्त कर सकते हैं नीचे दिए गए आंकड़े में, 1 और 2 5 के पहले छोटे हैं

ठीक है, मान लें कि हम इसे प्रत्येक बार के लिए ओ (1) समय में कर सकते हैं, तो हम इस समस्या को ओ (एन) में हल कर सकते हैं! प्रत्येक बार स्कैन करके

फिर, सवाल ये आता है: हर पट्टी के लिए, क्या हम वास्तव में ओ (1) समय में अपनी बाईं ओर और उसके दाहिनी ओर पहली छोटी बार पा सकते हैं? यह असंभव लगता है सही है? ... यह बढ़ती स्टैक का उपयोग कर संभव है।

बढ़ते स्टैक का उपयोग करके बाएं और दाएं पर पहले छोटे पर नज़र रख सकते हैं?

शायद आपको यह बता कर कि एक बढ़ती ढेर काम कर सकता है सब पर भरोसा नहीं है, इसलिए मैं आपको इस माध्यम से चलना होगा।

सबसे पहले, स्टैक बढ़ाने के लिए, हमें एक ऑपरेशन की आवश्यकता है:

while x < stack.top():
    stack.pop()
stack.push(x)

इसके बाद आप उस stack[x] लिए बढ़ते स्टैक में (जैसा कि नीचे दर्शाया गया है) की जांच कर सकते हैं, stack[x-1] उसके बाईं ओर पहला छोटा है, फिर एक नया तत्व जो stack[x] को पॉप कर सकता है वह पहला है छोटे दायें

फिर भी स्टैक पर विश्वास नहीं कर सकता [x-1] स्टैक [x] पर बाईं ओर पहला छोटा है?

मैं इसे विरोधाभास से साबित कर दूंगा।

सबसे पहले, stack[x-1] < stack[x] सुनिश्चित करने के लिए है लेकिन चलो मान लें stack[x-1] stack[x] के बाईं ओर पहले छोटा नहीं है stack[x]

तो जहां पहले छोटे fs ?

If fs < stack[x-1]:
    stack[x-1] will be popped out by fs,
else fs >= stack[x-1]:
    fs shall be pushed into stack,
Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x].

इसलिए स्टैक [x-1] पहले छोटे होना चाहिए।

सारांश:

बढ़ती ढेर प्रत्येक तत्व के लिए बाएं और दाएं पर पहले छोटे का ट्रैक रख सकता है। इस संपत्ति का उपयोग करके, हिस्टोग्राम में अधिक से अधिक आयत को ओ (एन) में एक स्टैक का उपयोग करके हल किया जा सकता है।

बधाई! यह वास्तव में एक कठिन समस्या है, मुझे खुशी है कि मेरी निराशाजनक व्याख्या आपको खत्म करने से नहीं रोकती थी अटैच किया गया मेरा साबित समाधान आपके इनाम के रूप में है :)

def largestRectangleArea(A):
    ans = 0
    A = [-1] + A
    A.append(-1)
    n = len(A)
    stack = [0]  # store index

    for i in range(n):
        while A[i] < A[stack[-1]]:
            h = A[stack.pop()]
            area = h*(i-stack[-1]-1)
            ans = max(ans, area)
        stack.append(i)
    return ans

ब्रूट बल दृष्टिकोण के अलावा इस समस्या को हल करने के तीन तरीके हैं। मैं उन सभी को लिखूंगा जावा कोड ने एक ऑनलाइन जज साइट में लीटकोड नामक परीक्षा पास की है: http://www.leetcode.com/onlinejudge#question_84 इसलिए मुझे विश्वास है कि कोड सही हैं I

समाधान 1: गतिशील प्रोग्रामिंग + n * n मैट्रिक्स कैश के रूप में

समय: हे (एन ^ 2), अंतरिक्ष: ओ (एन ^ 2)

मूल विचार: बार [आई] और बार [जे] के बीच न्यूनतम ऊंचाई कैश करने के लिए n * n मैट्रिक्स डीपी [आई] [जे] का उपयोग करें। चौड़ाई 1 के आयतों से मैट्रिक्स भरना प्रारंभ करें

public int solution1(int[] height) {

    int n = height.length;
    if(n == 0) return 0;
    int[][] dp = new int[n][n];        
    int max = Integer.MIN_VALUE;

    for(int width = 1; width <= n; width++){

        for(int l = 0; l+width-1 < n; l++){

            int r = l + width - 1;

            if(width == 1){
                dp[l][l] = height[l];
                max = Math.max(max, dp[l][l]);
            } else {                    
                dp[l][r] = Math.min(dp[l][r-1], height[r]);
                max = Math.max(max, dp[l][r] * width);
            }                
        }
    }

    return max;
}

समाधान 2: गतिशील प्रोग्रामिंग + कैश के रूप में 2 एरेज़

समय: हे (एन ^ 2), स्थान: ओ (एन)

मूल विचार: यह समाधान समाधान 1 जैसा है, लेकिन कुछ स्थान बचाता है। विचार यह है कि समाधान 1 में हम पंक्ति 1 से पंक्ति n तक मैट्रिक्स बनाते हैं। लेकिन प्रत्येक आवृत्ति में, केवल पिछली पंक्ति मौजूदा पंक्ति के निर्माण में योगदान करती है इसलिए हम पिछली पंक्ति के रूप में दो सरणियों का उपयोग करते हैं और चालू पंक्तियों को बदलते हैं।

public int Solution2(int[] height) {

    int n = height.length;
    if(n == 0) return 0;

    int max = Integer.MIN_VALUE;

    // dp[0] and dp[1] take turns to be the "previous" line.
    int[][] dp = new int[2][n];      

    for(int width = 1; width <= n; width++){

        for(int l = 0; l+width-1 < n; l++){

            if(width == 1){
                dp[width%2][l] = height[l];
            } else {
                dp[width%2][l] = Math.min(dp[1-width%2][l], height[l+width-1]);                     
            }
            max = Math.max(max, dp[width%2][l] * width);   
        }
    }        
    return max;
}

समाधान 3: स्टैक का उपयोग करें

समय: हे (एन), स्थान: ओ (एन)

यह समाधान मुश्किल है और मैंने ग्राफ़ के बिना स्पष्टीकरण से यह कैसे करना है और ग्राफ के साथ स्पष्टीकरण दिया है । मेरा सुझाव है कि आप नीचे दिए गए विवरण को पढ़ने से पहले दो लिंक पढ़ें। ग्राफ़ के बिना समझाना कठिन है, इसलिए मेरा स्पष्टीकरण कठिन हो सकता है

मेरे स्पष्टीकरण निम्नलिखित हैं:

  1. प्रत्येक बार के लिए, हमें इस बार वाले सबसे बड़े आयत को खोजने में सक्षम होना चाहिए। इसलिए इन एन आयतों में से सबसे बड़ी एक है जो हम चाहते हैं।

  2. एक निश्चित पट्टी के लिए सबसे बड़ा आयत प्राप्त करने के लिए (हम कहते हैं कि बार [i], (i + 1) वें बार), हमें इस बार को शामिल करने वाला सबसे बड़ा अंतराल पता होना चाहिए। हमें क्या पता है कि इस अंतराल में सभी बार बार [i] के साथ कम से कम समान ऊंचाई होना चाहिए। इसलिए यदि हम समझते हैं कि बार-बार तत्काल बाईं तरफ कितनी ही ऊंची ऊंचाई या उच्चतर बार हैं, और बार के तत्काल दाव पर कितने लगातार एक ही ऊंचाई या उच्चतर बार हैं [ i], हम अंतराल की लंबाई को जानते होंगे, जो बार [आई] के लिए सबसे बड़ी आयताकार की चौड़ाई है।

  3. बार [i] के तत्काल बाईं तरफ लगातार एक ही-ऊँचाई या उच्चतर बार की संख्या की गणना करने के लिए, हमें बाईं ओर सबसे निकटतम पट्टी खोजने की जरूरत है जो कि बार [i] से कम है, क्योंकि सभी सलाखों के बीच इस बार और बार [i] लगातार एक ही-ऊंचाई-या-उच्चतर बार होंगे

  4. हम एक स्टैक का इस्तेमाल सभी पट्टियों के नीचे के सभी बायां सलाखों को गतिशील रूप से ट्रैक करने के लिए करते हैं। दूसरे शब्दों में, यदि हम पहली बार बार बार [i] से दोहराते हैं, जब हम केवल बार [i] पर पहुंचते हैं और स्टैक को अपडेट नहीं करते हैं, तो स्टैक को उन सभी सलाखों को स्टोर करना चाहिए जो बार से अधिक नहीं हैं [i -1], जिसमें बार [आई-1] भी शामिल है हम बार [i] की ऊंचाई को ढेर में हर पट्टी के साथ तुलना करते हैं जब तक कि हम एक बार बार [आई] से कम नहीं मिलते हैं, जो कि क्लाउस्ट छोटा बार है। यदि बार [i] स्टैक में सभी सलाखों के मुकाबले अधिक है, तो इसका मतलब है कि बार के बाईं ओर सभी सलाखों [i] बार [i] से अधिक हैं।

  5. हम आई-वें बार के दाईं ओर एक ही चीज़ कर सकते हैं तब हम बार के लिए जानते हैं [i] अंतराल में कितनी बार हैं

    public int solution3(int[] height) {
    
        int n = height.length;
        if(n == 0) return 0;
    
        Stack<Integer> left = new Stack<Integer>();
        Stack<Integer> right = new Stack<Integer>();
    
        int[] width = new int[n];// widths of intervals.
        Arrays.fill(width, 1);// all intervals should at least be 1 unit wide.
    
        for(int i = 0; i < n; i++){
            // count # of consecutive higher bars on the left of the (i+1)th bar
            while(!left.isEmpty() && height[i] <= height[left.peek()]){
                // while there are bars stored in the stack, we check the bar on the top of the stack.
                left.pop();                
            }
    
            if(left.isEmpty()){
                // all elements on the left are larger than height[i].
                width[i] += i;
            } else {
                // bar[left.peek()] is the closest shorter bar.
                width[i] += i - left.peek() - 1;
            }
            left.push(i);
        }
    
        for (int i = n-1; i >=0; i--) {
    
            while(!right.isEmpty() && height[i] <= height[right.peek()]){                
                right.pop();                
            }
    
            if(right.isEmpty()){
                // all elements to the right are larger than height[i]
                width[i] += n - 1 - i;
            } else {
                width[i] += right.peek() - i - 1;
            }
            right.push(i);
        }
    
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            // find the maximum value of all rectangle areas.
            max = Math.max(max, width[i] * height[i]);
        }
    
        return max;
    }
    

मैं अन्य प्रविष्टियों को समझ नहीं पा रहा हूं, लेकिन मुझे लगता है कि मुझे ये पता है कि ओ (एन) में ऐसा कैसे करना है।

ए) प्रत्येक इंडेक्स के लिए हिस्टोग्राम के भीतर सबसे बड़ा आयताकार लगता है उस सूचकांक में समाप्त होता है जहां सूचकांक स्तंभ आयत के शीर्ष को छूता है और याद रखता है कि आयताकार कहाँ शुरू होता है। यह ओ (एन) में एक स्टैक आधारित एल्गोरिथम का उपयोग किया जा सकता है।

बी) इसी प्रकार प्रत्येक इंडेक्स के लिए उस इंडेक्स से शुरू होने वाला सबसे बड़ा आयत लगता है जहां सूचकांक स्तंभ आयत के शीर्ष को छूता है और याद रखता है कि आयताकार समाप्त होता है। इसके अलावा ओ (एन) उसी पद्धति का उपयोग करते हुए (ए) के रूप में, लेकिन हिस्टोग्राम को पीछे की तरफ स्कैन कर रहा है।

सी) प्रत्येक सूचकांक के लिए (ए) और (बी) के सबसे बड़े आयत को निर्धारित करने के लिए परिणाम मिलते हैं जहां उस सूचक पर कॉलम आयताकार के ऊपर छूती है। ओ (एन) की तरह (ए)

डी) सबसे बड़ा आयत हिस्टोग्राम के कुछ कॉलम से छूना चाहिए क्योंकि सबसे बड़ा आयत चरण (सी) में पाया सबसे बड़ा आयत है।

कठिन हिस्सा (ए) और (बी) को लागू कर रहा है, जो मुझे लगता है कि जेएफ सेबस्टियन ने सामान्य समस्या के बजाय हल किया हो सकता है।


विभाजन और जीत हासिल करने के लिए एक और उपाय भी है। इसके लिए एल्गोरिथ्म है:

1) ब्रेकिंग पॉइंट के रूप में छोटी ऊंचाई के साथ 2 भागों में सरणी को विभाजित करें

2) अधिकतम क्षेत्र अधिकतम है: ए) सरणी का सबसे छोटा ऊंचाई * आकार b) बायां आधा आर्डर में अधिकतम आयत c) अधिकतम आकृति में सही आधा सरणी

समय जटिलता ओ (nlogn) के लिए आता है


स्टैक समाधान अब तक के सबसे चतुर समाधानों में से एक है। और यह समझने में बहुत मुश्किल हो सकता है कि यह काम क्यों करता है

मैंने कुछ विस्तार से इसे समझाया है

पोस्ट से सारांश अंक: -

  • हमारा मस्तिष्क सामान्य तरीके से सोचता है: -
    • हर परिस्थिति बनाएँ और समस्या का समाधान करने के लिए आवश्यक संवेदना का मूल्य खोजने का प्रयास करें।
    • और हम खुशी से कोड को उस रूप में परिवर्तित करते हैं: - प्रत्येक स्थिति के लिए प्रतिबन्ध (न्यूनतम) का मूल्य ढूंढें (जोड़ी (आई, जे))

चतुर समाधान समस्या को फ्लिप करने की कोशिश करता है था क्षेत्र के प्रत्येक constraint/min मूल्य के लिए, सबसे अच्छा संभव और बाएँ चरमतम क्या है?

  • इसलिए यदि हम सरणी में प्रत्येक संभव min पर चलते हैं प्रत्येक मान के लिए बाएं और दाएँ चरम सीमाएं क्या हैं?

    • थोड़ा सोचा है कि, सबसे पहले सबसे कम मूल्य current min से कम होता है और इसी तरह पहले current min मूल्य जो कि वर्तमान न्यूनतम से कम है
  • तो अब हमें यह देखने की जरूरत है कि मौजूदा मूल्य से कम होने वाले पहले बाएं और दाएं मूल्यों को खोजने के लिए हमें एक चतुर तरीका मिल सकता है।

  • सोचने के लिए : अगर हम सरणी को आंशिक रूप से कहते हैं तो min_i तक, min_i + 1 का समाधान कैसे बनाया जा सकता है?

  • हमें इसकी बाईं ओर min_i से कम पहले मूल्य की आवश्यकता है

  • कथन को उलटा देना: हमें min_i की बाईं ओर सभी मानों को अनदेखा करने की आवश्यकता है जो min_i से अधिक है जब हम न्यूनतम मूल्य min_i (i) से छोटा पाते हैं तो हम रोकते हैं। एक बार जब हम इसे पार कर चुके हैं तो वक्र में गर्त बेकार हो जाते हैं । हिस्टोग्राम में, (2 4 3) => यदि 3 है min_i, 4 बड़ा होना ब्याज की नहीं है
  • कोररल : एक श्रेणी में (i, j)। जम्मू न्यूनतम मूल्य है जिसे हम सोच रहे हैं .. जम्मू और इसके बाएं मूल्य के बीच के सभी मूल्य मैं बेकार हैं I आगे की गणना के लिए भी
  • जम्मू से बड़ा न्यूनतम मूल्य वाले किसी भी हिस्टोग्राम को जम्मू पर बांध दिया जाएगा। बायीं तरफ ब्याज के मूल्यों में मोनोटोनिक रूप से बढ़ते अनुक्रम के रूप में जे सबसे बड़ा मूल्य है। (ब्याज की कीमत यहां संभावित मूल्य है जो बाद के सरणी के लिए ब्याज की हो सकती है)
  • चूंकि, हम हर मिनट मूल्य / वर्तमान मूल्य के लिए, बाएं से दाएं यात्रा कर रहे हैं - हमें पता नहीं है कि सरणी के दाहिने ओर से एक तत्व छोटा होगा या नहीं
    • तो हमें इसे स्मृति में रखना चाहिए जब तक हमें यह पता न पड़े कि यह मान बेकार है। (चूंकि एक छोटे मूल्य पाया जाता है)
  • यह सब हमारे अपने stack संरचना का उपयोग करने के लिए ले जाता है

    • हम स्टैक पर रहते हैं जब तक हम इसकी बेकार नहीं जानते।
    • जब हम जानते हैं कि हम बात बकवास है तो हम स्टैक से निकाल देते हैं।
  • इसलिए प्रत्येक न्यूनतम मूल्य के लिए इसके बाएं छोटे मान को खोजने के लिए, हम निम्नलिखित कार्य करते हैं: -

    1. इसके बड़े तत्वों को पॉप करें (बेकार मूल्य)
    2. मूल्य से छोटा पहला तत्व बाएं चरम है मैं हमारे मिनट के लिए
  • हम सरणी के दाहिनी ओर से एक ही चीज़ कर सकते हैं और हम अपने मिनट के लिए जम्मू को मिलेंगे।

यह समझाने में काफी मुश्किल है, लेकिन अगर यह समझ में आता है तो मैं सुझाव देता हूं कि यहां पूरा लेख पढ़ा क्योंकि इसमें अधिक अंतर्दृष्टि और विवरण हैं।