班级网站建设模板下载,企业年金查询官网,江西工厂网站建设,wordpress热门文章题目
柱状图中的最大的矩形
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。
示例 1: 输入#xff1a;heights [2,1,5,6,2,3]
输出#xff1a;10
…题目
柱状图中的最大的矩形
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
示例 1: 输入heights [2,1,5,6,2,3]
输出10
解释最大的矩形为图中红色区域面积为 10示例 2 输入 heights [2,4]
输出 4提示
1 heights.length 1050 heights[i] 104
题解 枚举高度预处理l r class Solution {public int largestRectangleArea(int[] heights) {int ans 0;DequeInteger st new ArrayDeque();int n heights.length;//l[i]为左边最近的比其小的下标 r[i]为右边最近的比其小的下标int[] l new int[n], r new int[n];Arrays.fill(l, -1);// 初始化-1Arrays.fill(r, n);// 初始化nfor (int i 0; i n; i) {while (!st.isEmpty() heights[i] heights[st.peekLast()]) {r[st.pollLast()] i;}st.addLast(i);}st.clear();for (int i n - 1; i 0; i--) {while (!st.isEmpty() heights[i] heights[st.peekLast()]) {l[st.pollLast()] i;}st.addLast(i);}for (int i 0; i n; i) {int h heights[i];ans Math.max(ans, (r[i] - l[i] - 1) * h);}return ans;}
}
