2014
11-18

# LeetCode-Largest Rectangle in Histogram[栈]

### Largest Rectangle in Histogram

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.

For example,
Given height = [2,1,5,6,2,3],
return 10.

// LeetCode, Largest Rectangle in Histogram
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
stack<int> s;
height.push_back(0);
int result = 0;
for (int i = 0; i < height.size(); ) {
if (s.empty() || height[i] > height[s.top()])
s.push(i++);
else {
int tmp = s.top();
s.pop();
result = max(result,
height[tmp] * (s.empty() ? i : i - s.top() - 1));
}
}
return result;
}
};


Java代码:

public class Solution {

public static int largestRectangleArea (int heights[]){
if(heights.length == 0 ) return 0;
if(heights.length == 0) return heights[0];
int ans = 0;
int n = heights.length;
int left[] = new int[n+1];
int right[] = new int[n+1];
processLR(heights, left, right);
for(int i=1; i<=n; i++){
int tmp = (right[i]-left[i]+1) * heights[i-1];
if( ans < tmp)
ans = tmp;
}

return ans;
}

public static int processLR(int heights[], int left[], int right[]){
int n = heights.length;
//用临时数组，设置两个哨兵
int tempArr[] = new int[n+2];
tempArr[0] = -1;
for(int i=1; i<=n; i++) tempArr[i] = heights[i-1];
tempArr[tempArr.length-1] = -1;

for(int i=1; i<=n; i++){
int k = i;
while( tempArr[i] <= tempArr[k-1])
k = left[k-1];
left[i] = k;
}

for(int i=n; i>0; i--){
int k = i;
while(  tempArr[i] <= tempArr[k+1])
k = right[k+1];
right[i] = k;
}

return 0;
}
}

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

2. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

3. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

4. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。