网页制作与网站建设实战大全pdf,劳务公司找项目平台,重庆网站公司推荐,上海网页公司题目#xff1a;
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。
方法#xff1a; 代码#xff1a;
class Solution {public int largestRectang…题目
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
方法 代码
class Solution {public int largestRectangleArea(int[] hs) {int n hs.length;int[] l new int[n], r new int[n];Arrays.fill(l, -1); Arrays.fill(r, n);DequeInteger d new ArrayDeque();// 遍历填充 r 数组, r[i]表示位置 i 右边最近一个比其小的位置for (int i 0; i n; i) {while (!d.isEmpty() hs[d.peekLast()] hs[i]) r[d.pollLast()] i;d.addLast(i);}d.clear(); // 处理完 r 数组, 清空栈// 遍历填充 l 数组, l[i]表示位置 i 左边最近一个比其小的位置for (int i n - 1; i 0; i--) {while (!d.isEmpty() hs[d.peekLast()] hs[i]) l[d.pollLast()] i;d.addLast(i);}int ans 0;for (int i 0; i n; i) {int t hs[i], a l[i], b r[i];ans Math.max(ans, (b - a - 1) * t);}return ans;}
}
