做电影网站要懂代码,网站营销策略,开平建设局网站,公众号电影网站是怎么做的一、LeetCode84. 柱状图中最大的矩形
题目链接#xff1a;84. 柱状图中最大的矩形
题目描述#xff1a;
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的最大…一、LeetCode84. 柱状图中最大的矩形
题目链接84. 柱状图中最大的矩形
题目描述
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。 示例 1: 输入heights [2,1,5,6,2,3]
输出10
解释最大的矩形为图中红色区域面积为 10示例 2 输入 heights [2,4]
输出 4 提示
1 heights.length 1050 heights[i] 104
算法分析
直接上代码
class Solution {int largestRectangleArea(int[] heights) {StackInteger st new StackInteger();// 数组扩容在头和尾各加入一个元素int [] newHeights new int[heights.length 2];newHeights[0] 0;newHeights[newHeights.length - 1] 0;for (int index 0; index heights.length; index){newHeights[index 1] heights[index];}heights newHeights;st.push(0);int result 0;// 第一个元素已经入栈从下标1开始for (int i 1; i heights.length; i) {// 注意heights[i] 是和heights[st.top()] 比较 st.top()是下标if (heights[i] heights[st.peek()]) {st.push(i);} else if (heights[i] heights[st.peek()]) {st.pop(); // 这个可以加可以不加效果一样思路不同st.push(i);} else {while (heights[i] heights[st.peek()]) { // 注意是whileint mid st.peek();st.pop();int left st.peek();int right i;int w right - left - 1;int h heights[mid];result Math.max(result, w * h);}st.push(i);}}return result;}
}
