【Lintcode】122.Largest Rectangle in Histogram
2024-09-05 20:08:06
题目：
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
题解：
做编程题一定要自己AC了再去看discussion，之前一直草草的刷题，感觉忘得好快，尤其是边界条件的处理上一点长进也没有，这次hard题做了半个多小时，从开始看题到提交（提交了3次，都是小错误。。。太不细心了，这更加说明了白板编程的重要性，不要用IDE），完全自己码出来，以后会坚持这样做，否则去面试什么的肯定跪，也不利于思维逻辑能力的提高。
Solution 1 ()
class Solution {
public:
int largestRectangleArea(vector<int> height) {
if (height.empty()) return ;
stack<int> high;
int maxArea = ;
high.push();
height.push_back();
for (int i = ; i < height.size(); ++i) {
while (!high.empty() && height[i] < height[high.top()]) {
int index = high.top();
high.pop();
if (high.empty()) {
maxArea = max((i - ) * height[index], maxArea);
} else {
maxArea = max((i - high.top() - ) * height[index], maxArea);
}
}
high.push(i);
}
return maxArea;
}
};
Solution 2 ()
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int ret = ;
height.push_back();
vector<int> index;
for(int i = ; i < height.size(); i++) {
while(index.size() > && height[index.back()] >= height[i]) {
int h = height[index.back()];
index.pop_back();
int sidx = index.size() > ? index.back() : -;
if(h * (i-sidx-) > ret)
ret = h * (i-sidx-);
}
index.push_back(i);
}
return ret;
}
};
Diveide and Conquer 思想比较容易懂， 就是写起来的时候边界条件有点麻烦。
Solution 3 ()
class Solution {
int maxCombineArea(const vector<int> &height, int s, int m, int e) {
// Expand from the middle to find the max area containing height[m] and height[m+1]
int i = m, j = m+;
int area = , h = min(height[i], height[j]);
while(i >= s && j <= e) {
h = min(h, min(height[i], height[j]));
area = max(area, (j-i+) * h);
if (i == s) {
++j;
}
else if (j == e) {
--i;
}
else {
// if both sides have not reached the boundary,
// compare the outer bars and expand towards the bigger side
if (height[i-] > height[j+]) {
--i;
}
else {
++j;
}
}
}
return area;
}
int maxArea(const vector<int> &height, int s, int e) {
// if the range only contains one bar, return its height as area
if (s == e) {
return height[s];
}
// otherwise, divide & conquer, the max area must be among the following 3 values
int m = s + (e-s)/;
// 1 - max area from left half
int area = maxArea(height, s, m);
// 2 - max area from right half
area = max(area, maxArea(height, m+, e));
// 3 - max area across the middle
area = max(area, maxCombineArea(height, s, m, e));
return area;
}
public:
int largestRectangleArea(vector<int> &height) {
if (height.empty()) {
return ;
}
return maxArea(height, , height.size()-);
}
};
为什么下面的代码过不了？？？
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
if (height.empty()) return ;
return maxArea(height, , height.size() - );
}
int maxArea(vector<int> height, int begin, int end) {
if (begin == end) {
return height[begin];
}
int mid = begin + (end - begin) / ;
int mArea = maxArea(height, begin, mid);
mArea = max(mArea, maxArea(height, mid + , end));
mArea = max(mArea, maxCombineArea(height, begin, mid, end));
return mArea;
}
int maxCombineArea(vector<int> height, int begin, int mid, int end) {
int maxArea = ;
int left = mid, right = mid + ;
int high = min(height[left], height[right]);
while (left >= begin && right <= end) {
high = min(high, min(height[left], height[right]));
maxArea = max(maxArea, (right - left + ) * high);
if (left == begin) {
++right;
} else if (right == end) {
--left;
} else {
if (height[left - ] > height[right + ]) {
--left;
} else {
++right;
}
}
}
return maxArea;
}
};
最新文章
- Markdown编辑器：Typora
- php导出csv数据在浏览器中输出提供下载或保存到文件的示例
- Netty关闭客户端
- Android之Android studio安装
- Android LayoutInflater&LayoutInflaterCompat源码解析
- rails 中 create, new, build, save 的用法以及误区汇总
- 浅析门户网站体育赛事CDN加速解决方案
- 《招聘一个靠谱的iOS》面试题参考答案（上）
- ECOS-Mongodb安装
- openstack私有云布署实践【14.1 登录页dashboard-controller（科兴环境）】
- mysql字符集问题
- node环境安装(mac版和windows版)
- 通过url获取相应的location信息
- [LeetCode] Find Smallest Letter Greater Than Target 找比目标值大的最小字母
- android AlarmManager讲解
- vue element-ui 2.3.4版本 input number值为0时 显示不出来
- Kestrel:Net Core的跨平台服务器
- 蓝桥杯 算法提高 8皇后·改 -- DFS 回溯
- Jmeter+Ant+Jenkins搭建持续集成的接口测试框架
- sql 存储过程返回值 变量名