leetcode-0085

题目

最大矩形

关键词：

单调栈

思路：

逐行按列累加'1'的个数，遇到0则清0，并逐行将下标入栈，保持栈内单调递增，（相等则视为非递增）。注意最后栈可能非空，检查栈顶值是否为-1。矩形面积=宽度*高度。

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

//#define MY_DEBUG printf
#define MY_DEBUG
#define MLOGD
//#define MLOGD       MY_DEBUG
#define MLOGI       MY_DEBUG
#define MLOGE       MY_DEBUG

#define MIN(x, y)       ((x) < (y) ? (x) : (y))
#define MAX(x, y)       ((x) > (y) ? (x) : (y))
#define ARRAY_SIZE(x)   (sizeof(x)/sizeof(x[0]))

typedef struct {
    int *buf;
    int top;
    int size;
} MyStackType;

static MyStackType g_stack = {
        .buf = NULL,
        .top = 0,
        .size = 0
};

int StackPush(int val)
{
    if (g_stack.top >= g_stack.size) {
        MLOGE("g_stack.top=%d is out of range[%d]\n", g_stack.top, g_stack.size);
        return -1;
    }
    MLOGD("---------------------push %d\n", val);
    g_stack.buf[g_stack.top++] = val;
    return 0;
}

int StackPop(void)
{
    if (g_stack.top <= 0) {
        MLOGE("empty stack\n");
        return -1;
    }
    MLOGD("=====================pop %d\n", g_stack.buf[g_stack.top - 1]);
    return g_stack.buf[--g_stack.top];
}

int GetStackPeek(void)
{
    if (g_stack.top > 0) {
        return g_stack.buf[g_stack.top - 1];
    }
    return -1;
}

int StackInit(int size)
{
    if (size <= 0) {
        return -1;
    }
    g_stack.buf = (int *)malloc(size * sizeof(int));
    if (g_stack.buf == NULL) {
        return -1;
    }
    g_stack.size = size;
    g_stack.top = 0;
    return 0;
}

void StackDeInit(void)
{
    if (g_stack.buf != NULL) {
        free(g_stack.buf);
        g_stack.buf = NULL;
    }
    g_stack.size = 0;
    g_stack.top = -1;
}

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize)
{
    if ((matrix == NULL) || (matrixSize <= 0)) {
        MLOGE("invalid arg\n");
        return 0;
    }
    int i, j;
    int colMaxSize = 0;
    for (i = 0; i < matrixSize; i++) {
        colMaxSize = MAX(colMaxSize, matrixColSize[i]);
    }
    int *tempCol = (int *)malloc(colMaxSize * sizeof(int));
    if (tempCol == NULL) {
        MLOGE("malloc\n");
        return 0;
    }
    memset(tempCol, 0, colMaxSize * sizeof(int));
    int ret = StackInit(colMaxSize + 1);
    if (ret < 0) {
        MLOGE("stack init error\n");
        free(tempCol);
        return 0;
    }
    int maxSize = 0;
    int topIdx;
    char *tmpColPtr;
    int curVal;
    MLOGI("matrixSize=%d\n", matrixSize);
    for(i = 0; i < matrixSize; i++) {
        g_stack.top = 0;
        StackPush(-1);
        tmpColPtr = matrix[i];
        for (j = 0; j < matrixColSize[i]; j++) {
            tempCol[j] = (tmpColPtr[j] == '0')  ? 0 : (1 + tempCol[j]);
            MLOGI("matrix[%d][%d]=%d, tempCol[%d]=%d\n", i, j, tmpColPtr[j] - '0', j, tempCol[j]);
            MLOGI("GetStackPeek()=%d, tempCol[GetStackPeek()]=%d\n", GetStackPeek(), tempCol[GetStackPeek()]);
            while ((GetStackPeek() != -1) && (tempCol[j] <= tempCol[GetStackPeek()])) {
                topIdx = StackPop();
                curVal = (j - 1 - g_stack.buf[g_stack.top - 1]) * tempCol[topIdx];
                MLOGI("i=%d, j=%d, tempCol[j]=%d, topIdx=%d, tempCol[topIdx]=%d, curVal=%d\n", i, j, tempCol[j], topIdx, tempCol[topIdx], curVal);
                maxSize = MAX(maxSize, curVal);
            }
            if (maxSize < tempCol[j]) {
                maxSize = tempCol[j];
            }
            StackPush(j);
        }
        MLOGI("------------------maxSize=%d, curVal=%d\n", maxSize, curVal);
        while (GetStackPeek() != -1) {
            /* stack may not be empty here, so you'll need to calculate the for the last value in the stack, width * height
             * the height is the peek value of the stack;
             * while the width is the full_width - the left_bar' offset
             */
            topIdx = StackPop();
            int tmp_height = tempCol[topIdx];
            int left_offset = g_stack.buf[g_stack.top - 1];
            int tmp_widht = matrixColSize[i] - left_offset - 1;
            MLOGI("topIdx=%d, tmp_height=%d, tmp_widht=%d, left_offset=%d\n", topIdx, tmp_height, tmp_widht, g_stack.buf[g_stack.top - 1]);
            maxSize = MAX(maxSize, tmp_widht * tmp_height);
            MLOGI("### maxSize=%d\n", maxSize);
        }
    }
    free(tempCol);
    StackDeInit();
    MLOGI("$$$$$$$$$$$$$$$$$$$$$$$$$maxSize=%d\n", maxSize);
    return maxSize;
}