سؤال

ما هي الخوارزمية الأكثر فعالية للعثور على المستطيل ذي المساحة الأكبر الذي يتناسب مع المساحة الفارغة؟

لنفترض أن الشاشة تبدو هكذا (يمثل "#" المساحة المملوءة):

....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............

الحل المحتمل هو:

....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...

عادةً ما أستمتع بإيجاد حل.على الرغم من أنني أرغب هذه المرة في تجنب إضاعة الوقت في التحسس بمفردي نظرًا لأن هذا له استخدام عملي لمشروع أعمل عليه.هل هناك حل معروف؟

شوغ9 كتب:

هل مدخلاتك عبارة عن مصفوفة (كما هو موضح في الاستجابات الأخرى)، أو قائمة من الاستثناءات في شكل مستطيلات ذات حجم عشوائي (كما قد يكون الحال في نظام النوافذ عند التعامل مع مواضع النوافذ)؟

نعم، لدي هيكل يتتبع مجموعة من النوافذ الموضوعة على الشاشة.لدي أيضًا شبكة تتتبع جميع المناطق الواقعة بين كل حافة، سواء كانت فارغة أو مملوءة، وموضع البكسل لحافتها اليسرى أو العلوية.أعتقد أن هناك بعض الأشكال المعدلة التي قد تستفيد من هذه الخاصية.هل تعرف أي؟

هل كانت مفيدة؟

المحلول 2

@lassevk

لقد وجدت المقالة المشار إليها من DDJ: مشكلة المستطيل الأقصى

نصائح أخرى

أنا مؤلف ذلك د.مقالة Dobb ويتم سؤالك أحيانًا عن التنفيذ.هنا واحدة بسيطة في C:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int one;
  int two;
} Pair;

Pair best_ll = { 0, 0 };
Pair best_ur = { -1, -1 };
int best_area = 0;

int *c; /* Cache */
Pair *s; /* Stack */
int top = 0; /* Top of stack */

void push(int a, int b) {
  s[top].one = a;
  s[top].two = b;
  ++top;
}

void pop(int *a, int *b) {
  --top;
  *a = s[top].one;
  *b = s[top].two;
}


int M, N; /* Dimension of input; M is length of a row. */

void update_cache() {
  int m;
  char b;
  for (m = 0; m!=M; ++m) {
    scanf(" %c", &b);
    fprintf(stderr, " %c", b);
    if (b=='0') {
      c[m] = 0;
    } else { ++c[m]; }
  }
  fprintf(stderr, "\n");
}


int main() {
  int m, n;
  scanf("%d %d", &M, &N);
  fprintf(stderr, "Reading %dx%d array (1 row == %d elements)\n", M, N, M);
  c = (int*)malloc((M+1)*sizeof(int));
  s = (Pair*)malloc((M+1)*sizeof(Pair));
  for (m = 0; m!=M+1; ++m) { c[m] = s[m].one = s[m].two = 0; }
  /* Main algorithm: */
  for (n = 0; n!=N; ++n) {
    int open_width = 0;
    update_cache();
    for (m = 0; m!=M+1; ++m) {
      if (c[m]>open_width) { /* Open new rectangle? */
        push(m, open_width);
        open_width = c[m];
      } else /* "else" optional here */
      if (c[m]<open_width) { /* Close rectangle(s)? */
        int m0, w0, area;
        do {
          pop(&m0, &w0);
          area = open_width*(m-m0);
          if (area>best_area) {
            best_area = area;
            best_ll.one = m0; best_ll.two = n;
            best_ur.one = m-1; best_ur.two = n-open_width+1;
          }
          open_width = w0;
        } while (c[m]<open_width);
        open_width = c[m];
        if (open_width!=0) {
          push(m0, w0);
        }
      }
    }
  }
  fprintf(stderr, "The maximal rectangle has area %d.\n", best_area);
  fprintf(stderr, "Location: [col=%d, row=%d] to [col=%d, row=%d]\n",
                  best_ll.one+1, best_ll.two+1, best_ur.one+1, best_ur.two+1);
  return 0;
}

يأخذ مدخلاته من وحدة التحكم.يمكنك على سبيل المثال.توجيه هذا الملف إليه:

16 12
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0
0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0
0 0 0 0 1 1 * * * * * * 0 0 1 0
0 0 0 0 0 0 * * * * * * 0 0 1 0
0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0
0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0

وبعد طباعة مدخلاته سيخرج:

The maximal rectangle has area 12.
Location: [col=7, row=6] to [col=12, row=5]

التنفيذ أعلاه ليس شيئًا خياليًا بالطبع، لكنه قريب جدًا من الشرح الموجود في دليل Dr.يجب أن تكون مقالة دوب سهلة الترجمة إلى كل ما هو مطلوب.

إليك صفحة تحتوي على بعض التعليمات البرمجية وبعض التحليلات.

مشكلتك الخاصة تبدأ قليلاً في الصفحة، ابحث في الصفحة عن النص مشكلة المستطيل الأقصى.

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html

@lassevk

    // 4. Outer double-for-loop to consider all possible positions 
    //    for topleft corner. 
    for (int i=0; i < M; i++) {
      for (int j=0; j < N; j++) {

        // 2.1 With (i,j) as topleft, consider all possible bottom-right corners. 

        for (int a=i; a < M; a++) {
          for (int b=j; b < N; b++) {

هاها...يا(م2ن2)..ربما هذا ما كنت سأتوصل إليه.

أرى أنهم يواصلون تطوير التحسينات ...تبدو جيدة، سآخذ قراءة.

لقد قمت بتنفيذ حل Dobbs في Java.

لا يوجد ضمان لأي شيء.

package com.test;

import java.util.Stack;

public class Test {

    public static void main(String[] args) {
        boolean[][] test2 = new boolean[][] { new boolean[] { false, true, true, false },
                new boolean[] { false, true, true, false }, new boolean[] { false, true, true, false },
                new boolean[] { false, true, false, false } };
        solution(test2);
    }

    private static class Point {
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int x;
        public int y;
    }

    public static int[] updateCache(int[] cache, boolean[] matrixRow, int MaxX) {
        for (int m = 0; m < MaxX; m++) {
            if (!matrixRow[m]) {
                cache[m] = 0;
            } else {
                cache[m]++;
            }
        }
        return cache;
    }

    public static void solution(boolean[][] matrix) {
        Point best_ll = new Point(0, 0);
        Point best_ur = new Point(-1, -1);
        int best_area = 0;

        final int MaxX = matrix[0].length;
        final int MaxY = matrix.length;

        Stack<Point> stack = new Stack<Point>();
        int[] cache = new int[MaxX + 1];

        for (int m = 0; m != MaxX + 1; m++) {
            cache[m] = 0;
        }

        for (int n = 0; n != MaxY; n++) {
            int openWidth = 0;
            cache = updateCache(cache, matrix[n], MaxX);
            for (int m = 0; m != MaxX + 1; m++) {
                if (cache[m] > openWidth) {
                    stack.push(new Point(m, openWidth));
                    openWidth = cache[m];
                } else if (cache[m] < openWidth) {
                    int area;
                    Point p;
                    do {
                        p = stack.pop();
                        area = openWidth * (m - p.x);
                        if (area > best_area) {
                            best_area = area;
                            best_ll.x = p.x;
                            best_ll.y = n;
                            best_ur.x = m - 1;
                            best_ur.y = n - openWidth + 1;
                        }
                        openWidth = p.y;
                    } while (cache[m] < openWidth);
                    openWidth = cache[m];
                    if (openWidth != 0) {
                        stack.push(p);
                    }
                }
            }
        }

        System.out.printf("The maximal rectangle has area %d.\n", best_area);
        System.out.printf("Location: [col=%d, row=%d] to [col=%d, row=%d]\n", best_ll.x + 1, best_ll.y + 1,
                best_ur.x + 1, best_ur.y + 1);
    }

}

بعد معاناة طويلة كتبت هذه الخوارزمية...فقط شاهد الكود...

أنت تفهم ذلك. هذا الرمز يتحدث !!

import java.util.Scanner;
import java.util.Stack;

/**
 * Created by BK on 05-08-2017.
 */
public class LargestRectangleUnderHistogram {
    public static void main(String... args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] input = new int[n];
        for (int j = 0; j < n; j++) {
            input[j] = scanner.nextInt();
        }



        /*
        *   This is the procedure used for solving :
        *
        *   Travel from first element to last element of the array
        *
        *   If stack is empty add current element to stack
        *
        *   If stack is not empty check for the top element of stack if
        *   it is smaller than the current element push into stack
        *
        *   If it is larger than the current element pop the stack until we get an
        *   element smaller than the current element or until stack becomes empty
        *
        *   After popping each element check if the stack is empty or not..
        *
        *   If stack is empty it means that this is the smallest element encountered till now
        *
        *   So we can multiply i with this element to get a big rectangle which is contributed by
        *
        *   this
        *
        *   If stack is not empty then check for individual areas(Not just one bar individual area means largest rectangle by this) (i-top)*input[top]
        *
        *
        * */

        /*
        * Initializing the maxarea as we check each area with maxarea
        */

        int maxarea = -1;
        int i = 0;
        Stack<Integer> stack = new Stack<>();
        for (i = 0; i < input.length; i++) {

            /*
            *   Pushing the element if stack is empty
            * */


            if (stack.isEmpty()) {
                stack.push(i);
            } else {

                /*
                *   If stack top element is less than current element push
                * */

                if (input[stack.peek()] < input[i]) {
                    stack.push(i);
                } else {

                    /*
                    *   Else pop until we encounter an element smaller than this in stack or stack becomes empty
                    *   
                    * */


                    while (!stack.isEmpty() && input[stack.peek()] > input[i]) {

                        int top = stack.pop();

                        /*
                        *   If stack is empty means this is the smallest element encountered so far
                        *   
                        *   So we can multiply this with i
                        * */

                        if (stack.isEmpty()) {
                            maxarea = maxarea < (input[top] * i) ? (input[top] * i) : maxarea;
                        }

                        /*
                         *  If stack is not empty we find areas of each individual rectangle
                         *  Remember we are in while loop
                         */

                        else {
                            maxarea = maxarea < (input[top] * (i - top)) ? (input[top] * (i - top)) : maxarea;
                        }
                    }
                    /*
                    *   Finally pushing the current element to stack
                    * */

                    stack.push(i);
                }
            }
        }

        /*
        *  This is for checking if stack is not empty after looping the last element of input
        *  
        *  This happens if input is like this 4 5 6 1 2 3 4 5
        *  
        *  Here 2 3 4 5 remains in stack as they are always increasing and we never got 
        *  
        *  a chance to pop them from stack by above process
        *  
        * */


        while (!stack.isEmpty()) {

            int top = stack.pop();

            maxarea = maxarea < (i - top) * input[top] ? (i - top) * input[top] : maxarea;
        }

        System.out.println(maxarea);
    }
}

أنا مؤلف كتاب حل المستطيل الأقصى على LeetCode، وهو ما تستند إليه هذه الإجابة.

نظرًا لأن الحل القائم على المكدس قد تمت مناقشته بالفعل في الإجابات الأخرى، أود أن أقدم الحل الأمثل O(NM) حل البرمجة الديناميكية الذي ينشأ من المستخدم morrischen2008.

حدس

تخيل خوارزمية حيث قمنا بحساب مستطيل لكل نقطة عن طريق القيام بما يلي:

  • العثور على أقصى ارتفاع للمستطيل من خلال التكرار لأعلى حتى الوصول إلى المساحة المملوءة

  • إيجاد أقصى عرض للمستطيل عن طريق التكرار للخارج يمينًا ويسارًا حتى يصل إلى ارتفاع لا يلائم الحد الأقصى لارتفاع المستطيل

على سبيل المثال، العثور على المستطيل المحدد بالنقطة الصفراء:enter image description here

نحن نعلم أن المستطيل الأقصى يجب أن يكون أحد المستطيلات التي تم إنشاؤها بهذه الطريقة (يجب أن يكون للمستطيل الأقصى نقطة على قاعدته حيث يقع المربع المملوء التالي ارتفاع فوق تلك النقطة).

لكل نقطة نحدد بعض المتغيرات:

h - ارتفاع المستطيل المحدد بتلك النقطة

l - الحد الأيسر للمستطيل المحدد بهذه النقطة

r - الحد الأيمن للمستطيل المحدد بهذه النقطة

تحدد هذه المتغيرات الثلاثة المستطيل بشكل فريد عند تلك النقطة.يمكننا حساب مساحة هذا المستطيل باستخدام h * (r - l).الحد الأقصى العالمي لجميع هذه المناطق هو نتيجتنا.

باستخدام البرمجة الديناميكية، يمكننا استخدام h, l, ، و r من كل نقطة في الصف السابق لحساب h, l, ، و r لكل نقطة في الصف التالي في الزمن الخطي.

خوارزمية

صف معين matrix[i], ، نحن نتتبع h, l, ، و r لكل نقطة في الصف عن طريق تحديد ثلاث صفائف - height, left, ، و right.

height[j] سوف تتوافق مع ارتفاع matrix[i][j], وهكذا مع المصفوفات الأخرى.

يصبح السؤال الآن كيفية تحديث كل مجموعة.

height

h يتم تعريفه على أنه عدد المساحات الشاغرة المستمرة في الخط من نقطتنا.نقوم بزيادة إذا كانت هناك مساحة جديدة، ونضبطها على الصفر إذا كانت المساحة ممتلئة (نستخدم "1" للإشارة إلى مساحة فارغة و"0" كمساحة ممتلئة).

new_height[j] = old_height[j] + 1 if row[j] == '1' else 0

left:

فكر في أسباب التغييرات في الحد الأيسر للمستطيل.نظرًا لأن جميع مثيلات المساحات المملوءة التي تحدث في الصف أعلى الصف الحالي قد تم بالفعل أخذها في الاعتبار في الإصدار الحالي من left, ، الشيء الوحيد الذي يؤثر علينا left هو إذا واجهنا مساحة مملوءة في صفنا الحالي.

ونتيجة لذلك يمكننا تحديد:

new_left[j] = max(old_left[j], cur_left)

cur_left هي واحدة أكبر من المساحة المملوءة في أقصى اليمين التي واجهناها.عندما نقوم "بتوسيع" المستطيل إلى اليسار، فإننا نعلم أنه لا يمكنه التوسع بعد تلك النقطة، وإلا فإنه سيمتد إلى المساحة المملوءة.

right:

هنا يمكننا إعادة استخدام تفكيرنا left وتعريف:

new_right[j] = min(old_right[j], cur_right)

cur_right هو الحدوث الموجود في أقصى اليسار للمساحة المملوءة التي واجهناها.

تطبيق

def maximalRectangle(matrix):
    if not matrix: return 0

    m = len(matrix)
    n = len(matrix[0])

    left = [0] * n # initialize left as the leftmost boundary possible
    right = [n] * n # initialize right as the rightmost boundary possible
    height = [0] * n

    maxarea = 0

    for i in range(m):

        cur_left, cur_right = 0, n
        # update height
        for j in range(n):
            if matrix[i][j] == '1': height[j] += 1
            else: height[j] = 0
        # update left
        for j in range(n):
            if matrix[i][j] == '1': left[j] = max(left[j], cur_left)
            else:
                left[j] = 0
                cur_left = j + 1
        # update right
        for j in range(n-1, -1, -1):
            if matrix[i][j] == '1': right[j] = min(right[j], cur_right)
            else:
                right[j] = n
                cur_right = j
        # update the area
        for j in range(n):
            maxarea = max(maxarea, height[j] * (right[j] - left[j]))

    return maxarea
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top