本文主要是介绍JAVA学习-练习试用Java实现“柱状图中最大的矩形 ”,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题:
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。
在图中用阴影勾勒出所能勾勒的最大矩形面积,其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
解答思路:
以下是使用 Java 实现的解法:
class Solution {public int largestRectangleArea(int[] heights) {int largest_rectangle = 0;int ls = heights.length;Deque<Integer> stack = new ArrayDeque<>();stack.push(-1);int top = 0, pos = 0;for (pos = 0; pos < ls; pos++) {while (top > 0 && heights[stack.peek()] > heights[pos]) {int tallest = stack.pop();top--;largest_rectangle = Math.max(largest_rectangle, heights[tallest] * (pos - stack.peek() - 1));}stack.push(pos);top++;}while (top > 0) {int tallest = stack.pop();top--;largest_rectangle = Math.max(largest_rectangle, heights[tallest] * (ls - stack.peek() - 1));}return largest_rectangle;}public static void main(String[] args) {int[] heights = {2, 1, 5, 6, 2, 3};Solution solution = new Solution();int result = solution.largestRectangleArea(heights);System.out.println("最大矩形面积:" + result);}
}
这段代码的思路是使用一个单调递增的栈来保存柱子的索引。在遍历高度数组时,如果当前高度小于栈顶元素的高度,就弹出栈顶元素,并计算以该元素为高的矩形面积。最后,再处理剩余栈中元素的矩形面积。通过这种方式,我们可以找到最大的矩形面积。
(文章为作者在学习java过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)
这篇关于JAVA学习-练习试用Java实现“柱状图中最大的矩形 ”的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!