LeetCode 84--Largest Rectangle in Histogram

本文主要是介绍LeetCode 84--Largest Rectangle in Histogram，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Largest Rectangle in Histogram
单调栈

class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> stack=new Stack<>();int maxArea=0,n=heights.length;for(int i=0;i<=n;i++){while(!stack.isEmpty() && (i==n || heights[stack.peek()]>heights[i]) ){int index=stack.pop();int h=heights[index];int w=stack.isEmpty()?i:i-stack.peek()-1;maxArea=Math.max(maxArea,h*w);}stack.push(i);}return maxArea;}
}

暴力解法

class Solution {public int largestRectangleArea(int[] heights) {int n=heights.length;int maxArea=0;for(int i=0;i<n;i++){int min_height=heights[i];for(int j=i;j>=0;j--){min_height=Math.min(min_height,heights[j]);maxArea=Math.max(maxArea,(i-j+1)*min_height);}}return maxArea;}
}

这篇关于LeetCode 84--Largest Rectangle in Histogram的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---