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;
}
文章评论