Хамгийн том тэг дэд матриц олох¶

Танд n мөр, m баганатай матриц өгөгдсөн. Зөвхөн тэгээс тогтох хамгийн том дэд матрицыг ол (дэд матриц гэдэг нь матрицын тэгш өнцөгт хэсэг юм).

Алгоритм¶

Матрицын элементүүд нь a[i][j] байх ба энд i = 0...n - 1, j = 0... m - 1. Энгийн байлгах үүднээс бид бүх тэг биш элементийг 1-тэй тэнцүү гэж үзнэ.

Алхам 1: Туслах динамик¶

Эхлээд бид дараах туслах матрицыг тооцоолно: d[i][j] нь a[i][j]-ийн дээр 1 байх хамгийн ойрын мөр. Албан ёсоор d[i][j] нь j-р баганад 1-тэй тэнцүү элемент байх хамгийн их мөрийн дугаар (0-ээс i - 1 хүртэл) юм. Зүүн дээрээс баруун доош давтахдаа i мөрөнд зогсох үед бид өмнөх мөрийн утгуудыг мэддэг тул зөвхөн 1 утгатай элементүүдийг шинэчлэхэд хангалттай. Бид утгуудыг энгийн d[i], i = 1...m - 1 массивт хадгалж болно, учир нь цаашдын алгоритмд бид матрицыг нэг мөрөөр нь боловсруулж, зөвхөн одоогийн мөрийн утгууд хэрэгтэй.

vector<int> d(m, -1);
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        if (a[i][j] == 1) {
            d[j] = i;
        }
    }
}

Алхам 2: Бодлого бодох¶

Бид бодлогыг мөрүүдээр давтаж, дэд матрицын бүх боломжит зүүн ба баруун баганыг авч үзэн $O(n m^2)$-д бодож болно. Тэгш өнцөгтийн доод тал нь одоогийн мөр байх ба d[i][j]-г ашиглан бид дээд мөрийг олж болно. Гэвч цааш явж, шийдлийн complexity-г эрс сайжруулах боломжтой.

Хайж буй тэг дэд матриц дөрвөн талаараа ямар нэг нэгжүүдээр хязгаарлагдсан бөгөөд эдгээр нь түүнийг хэмжээгээ ихэсгэж хариуг сайжруулахаас сэргийлдэг нь тодорхой. Тиймээс бид дараах байдлаар үйлдвэл хариуг алдахгүй: i мөр (боломжит тэг дэд матрицын доод мөр) дэх j нүд бүрийн хувьд бид d[i][j]-г одоогийн тэг дэд матрицын дээд мөр болгоно. Одоо тэг дэд матрицын оновчтой зүүн ба баруун заагийг тодорхойлох, өөрөөр хэлбэл энэ дэд матрицыг j-р баганаас зүүн ба баруун тийш хамгийн ихээр түлхэх нь үлдэж байна.

Зүүн тийш хамгийн ихээр түлхэнэ гэдэг нь юу гэсэн үг вэ? Энэ нь d[i][k1] > d[i][j] байх, мөн k1 нь j индексийн зүүн талд хамгийн ойр байх индекс k1-г олно гэсэн үг. Тэгвэл k1 + 1 нь шаардлагатай тэг дэд матрицын зүүн баганын дугаарыг өгнө гэдэг нь тодорхой. Хэрэв ийм индекс огт байхгүй бол k1 = -1 гэж тавь (энэ нь бид одоогийн тэг дэд матрицыг зүүн тийш a матрицын зах хүртэл сунгаж чадсан гэсэн үг).

Тэгш хэмтэйгээр та баруун заагийн хувьд k2 индексийг тодорхойлж болно: энэ нь d[i][k2] > d[i][j] байх j-ийн баруун талд хамгийн ойр индекс (эсвэл ийм индекс байхгүй бол m) юм.

Тэгэхээр k1 ба k2 индексүүд нь тэдгээрийг үр ашигтай хайж сурвал бидэнд одоогийн тэг дэд матрицын талаарх бүх шаардлагатай мэдээллийг өгнө. Тухайлбал түүний талбай нь (i - d[i][j]) * (k2 - k1 - 1)-тэй тэнцүү байна.

Тогтмол i ба j-тэй эдгээр k1 ба k2 индексүүдийг хэрхэн үр ашигтай хайх вэ? Бид үүнийг дунджаар $O(1)$-д хийж чадна.

Ийм complexity-д хүрэхийн тулд та стекийг дараах байдлаар ашиглаж болно. Эхлээд k1 индексийг хэрхэн хайхыг сурч, түүний утгыг одоогийн i мөр доторх j индекс бүрийн хувьд d1[i][j] матрицт хадгалъя. Үүний тулд бид бүх j баганыг зүүнээс баруун тийш харах ба стект зөвхөн d[][] нь d[i][j]-ээс чанд их байх баганыг хадгална. j баганаас дараагийн багана руу шилжихдээ стекийн агуулгыг шинэчлэх шаардлагатай нь тодорхой. Стекийн оройд тохиромжгүй элемент байвал (өөрөөр хэлбэл d[][] <= d[i][j]) түүнийг гарга. Стекээс зөвхөн оройноос нь хасахад л хангалттай бөгөөд бусад аль ч байрлалаас нь хасах шаардлагагүй гэдгийг ойлгоход амархан (учир нь стек нь баганануудын өсөх d дарааллыг агуулна).

j бүрийн хувьд d1[i][j] утга нь тухайн үед стекийн оройд байгаа утгатай тэнцүү байна.

k2 индексүүдийг олох d2[i][j] динамикийг үүнтэй адил авч үзэх ба зөвхөн баганануудыг баруунаас зүүн тийш харах хэрэгтэй.

Мөр бүрд яг m ширхэг стект нэмэгддэг тул устгалт ч түүнээс олон байх боломжгүй, complexity-ийн нийлбэр шугаман байх тул алгоритмын эцсийн complexity нь $O(nm)$ болно гэдэг нь тодорхой.

Мөн энэ алгоритм $O(m)$ санах ой зарцуулдгийг тэмдэглэх нь зүйтэй (оролтын өгөгдөл болох a[][] матрицыг тооцохгүй).

Implementation¶

int zero_matrix(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();

    int ans = 0;
    vector<int> d(m, -1), d1(m), d2(m);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 1)
                d[j] = i;
        }

        for (int j = 0; j < m; ++j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d1[j] = st.empty() ? -1 : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d2[j] = st.empty() ? m : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = 0; j < m; ++j)
            ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1));
    }
    return ans;
}