2019-11-26 138 views 评论

Leetcode题目解析（191126）：85&94

Leetcode 85：最大矩形

题目描述

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

代码实现

int maximalHistRec(vector&lt;int&gt;&amp; height) {
    stack&lt;int&gt; stackStore;
    int res = height[0];
    for (int i = 0; i &lt; height.size(); i++) {
        if (stackStore.empty() || height[i] &gt;= height[stackStore.top()])
            stackStore.push(i);
        else {
            while (!stackStore.empty() &amp;&amp; height[stackStore.top()] &gt; height[i]) {
                int ind = stackStore.top();
                stackStore.pop();
                res = max(res, stackStore.empty() ? height[ind] * i : height[ind] * (i - stackStore.top() - 1));
            }
            stackStore.push(i);
        }
    }
    return res;
}
int maximalRectangle(vector&lt;vector&lt;char&gt; &gt;&amp; matrix) {
    if (matrix.size() == 0)
        return 0;
    int res = 0;
    vector&lt;int&gt; height;
    for (int i = 0; i &lt; matrix[0].size(); i++) {
        if (matrix[0][i] == '1')
            height.push_back(1);
        else
            height.push_back(0);
    }
    height.push_back(0);
    res = maximalHistRec(height);
    for (int i = 1; i &lt; matrix.size(); i++) {
        for (int j = 0; j &lt; matrix[0].size(); j++) {
            if (matrix[i][j] == '1')
                height[j] += 1;
            else
                height[j] = 0;
        }
        res = max(res, maximalHistRec(height));
    }
    return res;
}

int maximalHistRec(vector<int>& height) {

stack<int> stackStore;

int res = height[0];

for (int i = 0; i < height.size(); i++) {

if (stackStore.empty() || height[i] >= height[stackStore.top()])

stackStore.push(i);

else {

while (!stackStore.empty() && height[stackStore.top()] > height[i]) {

int ind = stackStore.top();

stackStore.pop();

res = max(res, stackStore.empty() ? height[ind] * i : height[ind] * (i - stackStore.top() - 1));

}

stackStore.push(i);

}

return res;

}

int maximalRectangle(vector<vector<char> >& matrix) {

if (matrix.size() == 0)

return 0;

int res = 0;

vector<int> height;

for (int i = 0; i < matrix[0].size(); i++) {

if (matrix[0][i] == '1')

height.push_back(1);

else

height.push_back(0);

}

height.push_back(0);

res = maximalHistRec(height);

for (int i = 1; i < matrix.size(); i++) {

for (int j = 0; j < matrix[0].size(); j++) {

if (matrix[i][j] == '1')

height[j] += 1;

else

height[j] = 0;

}

res = max(res, maximalHistRec(height));

}

return res;

}

参考自：
https://www.nowcoder.com/profile/1941588/codeBookDetail?submissionId=12684718

执行用时&内存消耗

复杂度分析

Leetcode 94：二叉树的中序遍历

题目描述

给定一个二叉树，返回它的中序遍历。请使用迭代算法

代码实现

vector&lt;int&gt; inorderTraversal(TreeNode* root)
{
    stack&lt;TreeNode* &gt; stack;
    vector&lt;int&gt; res;
    TreeNode* tmp=root;
    while(tmp||stack.size())
    {
        while(tmp){
            stack.push(tmp);
            tmp=tmp-&gt;left;
        }
        tmp=stack.top();
        stack.pop();
        res.push_back(tmp-&gt;val);
        tmp=tmp-&gt;right;
    }
    return res;
}