Leetcode 85：最大矩形

题目描述

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

代码实现

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<int> inorderTraversal(TreeNode* root)
{
    stack<TreeNode* > stack;
    vector<int> res;
    TreeNode* tmp=root;
    while(tmp||stack.size())
    {
        while(tmp){
            stack.push(tmp);
            tmp=tmp->left;
        }
        tmp=stack.top();
        stack.pop();
        res.push_back(tmp->val);
        tmp=tmp->right;
    }
    return res;
}