题目:
给定 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);Deque<Integer> 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;}
}