青训营 X 豆包MarsCode 技术训练营--最大矩形面积问题

问题描述

小S最近在分析一个数组 h1,h2,…,hNh1​,h2​,…,hN​，数组的每个元素代表某种高度。小S对这些高度感兴趣的是，当我们选取任意 kk 个相邻元素时，如何计算它们所能形成的最大矩形面积。

对于 kk 个相邻的元素，我们定义其矩形的最大面积为：

R(k)=k×min(h[i],h[i+1],…,h[i+k−1])R(k)=k×min(h[i],h[i+1],…,h[i+k−1])

即，R(k)R(k) 的值为这 kk 个相邻元素中的最小值乘以 kk。现在，小S希望你能帮他找出对于任意 kk，R(k)R(k) 的最大值。
测试样例

样例1：

输入：n = 5, array = [1, 2, 3, 4, 5]
输出：9

样例2：

输入：n = 6, array = [5, 4, 3, 2, 1, 6]
输出：9

样例3：

输入：n = 4, array = [4, 4, 4, 4]
输出：16

解题思路

理解问题：我们需要找到数组中任意 k 个相邻元素所能形成的最大矩形面积。这个面积是由这 k 个元素中的最小高度乘以 k 得到的。
数据结构选择：我们可以使用单调栈来维护一个递增的高度序列，这样可以在 O(n) 时间内找到每个高度可以形成的最大矩形面积。
算法步骤：遍历数组中的每个高度。对于每个高度，使用单调栈来找到它左边和右边第一个比它小的位置。计算以当前高度为最小高度的矩形面积，并更新最大面积。 

代码

import java.util.*;
public class Main {
public static int solution(int n, int[] array) {
// 初始化最大面积为0
int maxArea = 0;

    // 使用单调栈来辅助计算Stack<Integer> stack = new Stack<>();// 遍历数组中的每个高度for (int i = 0; i < n; i++) {// 当栈不为空且当前高度小于栈顶高度时，计算以栈顶高度为最小高度的矩形面积while (!stack.isEmpty() && array[i] < array[stack.peek()]) {int height = array[stack.pop()];int width = stack.isEmpty() ? i : i - stack.peek() - 1;maxArea = Math.max(maxArea, height * width);}// 将当前高度的索引压入栈中stack.push(i);}// 处理栈中剩余的高度while (!stack.isEmpty()) {int height = array[stack.pop()];int width = stack.isEmpty() ? n : n - stack.peek() - 1;maxArea = Math.max(maxArea, height * width);}return maxArea;
}public static void main(String[] args) {// Add your test cases hereSystem.out.println(solution(5, new int[]{1, 2, 3, 4, 5}) == 9);System.out.println(solution(6, new int[]{5, 4, 3, 2, 1, 6}) == 9);System.out.println(solution(4, new int[]{4, 4, 4, 4}) == 16);
}

}