力扣84题：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
输入： heights = [2,4] 输出： 4
分析：
1. 其实，这一题就是找数组的最大相同部分，也就是说尽可能的找到各个柱子凑在一起，找出最大的共有部分。
2. 当然，如果其中一个柱子很高，而其他柱子很矮，那也有可能最大面积就取那个很高的柱子
3. 很显然，这一题跟柱子的高度以及所有柱子的共有部分有关。典型的单调栈结构
4. 既然是单调栈，那就假设没根柱子的高度是最大值，然后找左侧、右侧离当前柱子的最近距离。中间就是共有性质。
package code04.单调栈_01;
import java.util.Stack;
/**
* 力扣84题，柱状图中最大的矩形
* https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
*/
public class Code02_HistogramMaxRectangleCount {
public int largestRectangleArea(int[] heights)
{
if (heights == null || heights.length == 0) {
return 0;
}
int max = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < heights.length; i++) {
//以栈顶元素为高。如果出现比栈顶元素小的值，结束当前高度的左右扩展
while (!stack.isEmpty() && heights[stack.peek()] > heights[i])
{
int curIndex = stack.pop();
//如果有下标就减掉，没有下标说明从头开始，需要额外加1个。这里的-1用的很巧妙
int leftIndex = stack.isEmpty() ? -1 : stack.peek();
//i位置出现了小于当前说的情况，i位置的数不包含，因此需要往左移动一个
max = Math.max(max, heights[curIndex] * (i - 1 - leftIndex));
}
stack.push(i);
}
while (!stack.isEmpty()) {
int curIndex = stack.pop();
//如果有下标就减掉，没有下标说明从头开始，需要额外加1个。这里的-1用的很巧妙
int leftIndex = stack.isEmpty() ? -1 : stack.peek();
//heights.length - 1代表最后一个数的下标，是包含的。
max = Math.max(max, heights[curIndex] * (heights.length - 1 - leftIndex));
}
return max;
}
public static void main(String[] args) {
Code02_HistogramMaxRectangleCount ss = new Code02_HistogramMaxRectangleCount();
int[] heights = {2,1,5,6,2,3};
System.out.println(ss.largestRectangleArea(heights));
}
}
力扣85题：https://leetcode.cn/problems/maximal-rectangle
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。
上一题，我们是一维数组中求柱子的最大面积，而这一题却时二维数组。有没有办法也转换成一维数组呢？答案是有的。
思路：
1. 第一行最大面积为1, 因为所有的1都是断开的
2. 第一个和第二行数组压缩。得到2、0、2、1、1。 通过单调栈可以知道最大面积为3.
3. 前三行数组压缩，得到 3、1、3、2、2. 通过单调栈可得最大面积为6.
4. 所有行数组压缩，得到 4、0、0、3、0。 因为0代表是断开的，既然是断开的，那么之前行已经使用过了这些数据并且得到了
package code04.单调栈_01;
import java.util.Stack;
/**
* 力扣85题，最大矩形
* https://leetcode.cn/problems/maximal-rectangle/
*/
public class Code03_MaxRectangleCount {
public int maximalRectangle(char[][] matrix)
{
if (matrix == null || matrix.length == 0) {
return 0;
}
int[] dp = new int[matrix[0].length];
int ans = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
int cur = matrix[i][j] == '0' ? 0 : Integer.parseInt(String.valueOf(matrix[i][j]));
dp[j] = dp[j] + cur;
}
ans = Math.max(ans, largestRectangleArea(dp));
}
return ans;
}
public int largestRectangleArea(int[] heights)
{
int max = 0;
Stack<Integer> stack = new Stack();
for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
//当前列
int cur = stack.pop();
//当前列前一个比自己小的值的下标
int left = stack.isEmpty() ? -1 : stack.peek();
//范围内，当前列的高度为共性，求出最大公共部分值
max = Math.max(max, heights[cur] * (i - 1 - left));
}
stack.push(i);
}
while (!stack.isEmpty()) {
int cur = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
max = Math.max(max, heights[cur] * (heights.length - 1 - left));
}
return max;
}
public static void main(String[] args) {
Code03_MaxRectangleCount ss = new Code03_MaxRectangleCount();
char[][] matrix = {
{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
System.out.println(ss.maximalRectangle(matrix));
}
}
最大值。那么当前行就没有必要再次使用了。因此当前行某一列为0，那么数组压缩直接为0. 目测，我们就知道最大值为4.
5. 通过数组压缩以后，我们知道这个二维数组的最大值就为6.
