最大矩形

/*
 * 思路：
 * 1. 与普通的Java实现相似，只是在遍历数组和栈操作上使用Stream API。
 * 2. 使用Stream API将矩阵转换为高度数组，再计算每行的最大矩形面积。
 */
 
import java.util.Arrays;
import java.util.Stack;
 
public class MaximalRectangleStream {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int[] heights = new int[matrix[0].length];
        return Arrays.stream(matrix)
            .mapToInt(row -> {
                IntStream.range(0, row.length).forEach(j -> {
                    heights[j] = (row[j] == '1') ? heights[j] + 1 : 0;
                });
                return largestRectangleArea(heights);
            })
            .max()
            .orElse(0);
    }
 
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int index = 0;
        while (index < heights.length) {
            if (stack.isEmpty() || heights[index] >= heights[stack.peek()]) {
                stack.push(index);
                index++;
            } else {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? index : index - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? index : index - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        return maxArea;
    }
}