Encontrando a maior submatriz de 0's

Seja uma matriz com n linhas e m colunas. Encontre a maior submatriz(área retangular dentro da matriz) que consiste em apenas zeros.

Algoritmo

Os elementos da matriz serão a[i][j], onde i = 0...n - 1, j = 0... m - 1. Para simplificar, consideraremos todos os elementos diferentes de zero iguais a 1.

Etapa 1: dinâmica auxiliar

Primeiro, calculamos a seguinte matriz auxiliar: d[i][j], , linha mais próxima que tem 1 acima de a[i][j]. Formalmente, d[i][j] é o maior número de linha (de 0 a i - 1), no qual existe um elemento igual a 1 na j-ésima coluna. Ao iterar da parte superior esquerda para a parte inferior direita, quando estamos na linha i, conhecemos os valores da linha anterior; portanto, basta atualizar os elementos com o valor 1. Podemos salvar os valores em uma array simples d[i], i = 1...m - 1, porque no algoritmo adicional processaremos a matriz uma linha por vez e precisaremos apenas dos valores da linha atual.

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;
        }
    }
}

Etapa 2: Solução de problemas

Podemos resolver o problema em $O(n m^2)$ iterando pelas linhas, considerando todas as colunas esquerda e direita possíveis para uma submatriz. A parte inferior do retângulo será a linha atual e, usando d[i][j] podemos encontrar a linha superior. No entanto, é possível ir além e melhorar significativamente a complexidade da solução.

É claro que a submatriz de zeros desejada é delimitada em todos os quatro lados por alguns 1's, o que impede que ele aumente de tamanho e melhore a resposta. Portanto, não perderemos a resposta se agirmos da seguinte maneira: para cada célula j na linha i (a linha inferior de uma potencial submatriz zero) teremos d[i][j] como a linha superior da atual submatriz de zeros. Resta agora determinar os limites ideais esquerdo e direito da submatriz zero, ou seja, empurre ao máximo essa submatriz para a esquerda e direita da j-ésima coluna.

O que significa empurrar o máximo para a esquerda? Significa encontrar um índice k1 para o qual d[i][k1] > d[i][j], e, ao mesmo tempo, k1 - o mais próximo à esquerda do índice j. É claro que então k1 + 1 fornece o número da coluna esquerda da submatriz zero necessária. Se não houver esse índice, coloque k1 = -1(isso significa que conseguimos estender a submatriz de zeros atual para a esquerda até a borda da matriz a).

Simetricamente, você pode definir um índice k2 para a borda direita: este é o índice mais próximo à direita de j de modo que d[i][k2] > d[i][j] (ou m, se não houver esse índice).

Portanto, os índices k1 e k2, se aprendermos a procurá-los efetivamente, fornecerão todas as informações necessárias sobre a submatriz de zeros atual. Em particular, sua área será igual a (i - d[i][j]) * (k2 - k1 - 1).

Como procurar esses índices k1 e k2 efetivamente com fixos i e j? Podemos fazer isso em $O(1)$ em média.

Para atingir essa complexidade, você pode usar o stack da seguinte maneira. Vamos primeiro aprender a procurar um índice k1, e salvar seu valor para cada índice j na linha atual i na matriz d1[i][j]. Para fazer isso, examinaremos todas as colunas j da esquerda para a direita e armazenaremos no stack apenas as colunas que possuem d[][] estritamente maior que d[i][j]. É claro que, ao passar de uma coluna j para a próxima coluna, é necessário atualizar o conteúdo do stack. Quando houver um elemento inadequado no topo do stack (por exemplo, d[][] <= d[i][j]), remova-o. É fácil entender que basta remover do stack apenas do topo e de nenhum dos outros lugares (porque o stack conterá uma sequência crescente d de colunas).

O valor d1[i][j] para cada j será igual ao valor que está, naquele momento, no topo do stack.

A matriz dinâmica d2[i][j] para encontrar os índices k2 é considerada semelhante, apenas é necessário visualizar as colunas da direita para a esquerda.

Como existem exatamente m peças adicionadas ao stack em cada linha, também não poderia haver mais exclusões(deletar elementos), a soma das complexidades será linear, portanto a complexidade final do algoritmo é $O(nm)$.

Também deve ser observado que esse algoritmo consome $O(m)$ de memória (sem contar os dados de entrada - a matriz a[][]).

Implementação

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;
}