Givennnon-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 =10unit.
For example,Given height =[2,1,5,6,2,3],return10.
思路：此题还是有一些难度的，刚开始想的双指针，前后扫描，但是每次求最小的高度的时候都需要遍历一次，效率上不是很高。为o(n2)。
代码如下：
public class Solution {public int largestRectangleArea(int[] height) {int max = 0;//最大值int i = 0;//左指针int j = height.length – 1;//右指针boolean isMinChange = true;//双指针扫描while(i <= j){int minHeight = Integer.MAX_VALUE;//范围内最小值if(isMinChange){//最小值是否改变isMinChange = false;//重新得到最小值for(int k = i ; k <= j;k++){if(height[k] < minHeight){minHeight = height[k];}}}//面积int area = (j – i + 1)*minHeight;if(max < area){max = area;}if(i == j){//如果相等，则结束break;}if(height[i] < height[j]){//左指针增加，直到比当前大int k = i;while(k <= j && height[k] <= height[i]){if(height[k] == minHeight){//判断最小值是否改变isMinChange = true;}k++;}i = k;}else{//右指针减小，直到比当前大int k = j;while( k >= i && height[k] <= height[j]){if(height[k] == minHeight){//判断最小值是否改变isMinChange = true;}k–;}j = k;}}return max;}}
解法上过不了OJ,所以只能在网上参看资料，最后找到资料如下，是用栈解决的。
public class Solution {public int largestRectangleArea(int[] height) {if (height == null || height.length == 0) return 0;Stack<Integer> stHeight = new Stack<Integer>();Stack<Integer> stIndex = new Stack<Integer>();int max = 0;for(int i = 0; i < height.length; i++){if(stHeight.isEmpty() || height[i] > stHeight.peek()){stHeight.push(height[i]);stIndex.push(i);}else if(height[i] < stHeight.peek()){int lastIndex = 0;while(!stHeight.isEmpty() && height[i] < stHeight.peek()){lastIndex = stIndex.pop();int area = stHeight.pop()*(i – lastIndex);if(max < area){max = area;}}stHeight.push(height[i]);stIndex.push(lastIndex);}}while(!stHeight.isEmpty()){int area = stHeight.pop()*(height.length – stIndex.pop());max = max < area ? area:max;}return max;}}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
我不去想是否能够成功，既然选择了远方，便只顾风雨兼程！
