给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例1：
imageimage输入: [2,1,5,6,2,3]
输出: 10
Java解法
思路：
- 面积大小由宽高决定，考虑用滑动窗口来计算，记录最大的宽高积输出，发现没那么简单，
- 问题分解为以第i个位置为高时的最大面积，这样就就可以比较出最大的面积了，NICE
- 新问题，大量的重复数据导致严重超时，考虑用Set记录已存储的值，但这样会导致不同位置的值不一样的面积被掩盖，所以只能记录相等的值
- 跑不过用例，但是提交成功，一头雾水
package sj.shimmer.algorithm.m2;
/**
* Created by SJ on 2021/3/10.
*/
class D44 {
public static void main(String[] args) {
System.out.println(largestRectangleArea(new int[]{2,1,5,6,2,3}));
}
public static int largestRectangleArea(int[] heights) {
if (heights == null) {
return 0;
}
int length = heights.length;
long sum = 0;
int height = 0;
for (int i = 0; i < length; i++) {
int left = i;
int right = i;
if (height == heights[i]) {
continue;
}
height = heights[i];
while (left >= 0 && heights[left] >= height) {
left--;
}
while (right < length && heights[right] >= height) {
right++;
}
long temp = height * (right - left - 1);
sum = sum > temp ? sum : temp;
}
return (int) sum;
}
}
image
官方解
主要思路就是：枚举（宽或者高）
-
单调栈
emmm，用单调栈来计算左右边界，用一定空间节约了计算时间开销
- 时间复杂度：O(N)
- 空间复杂度：O(N)
-
单调栈 + 常数优化
优化了右边界的计算方式
- 时间复杂度：O(N)
- 空间复杂度：O(N)
