16. 最大矩形面积问题

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐ 中

问题描述

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

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

即，$R(k)$  的值为这 $k$ 个相邻元素中的最小值乘以 $k$。现在，小 S 希望你能帮他找出对于任意 $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 的最大值。这类似于经典的”最大矩形面积”问题，可以使用单调栈来高效解决。

关键思路：

1. 对于每个元素，我们需要找到以它为最小值的最大宽度区间；
2. 使用单调栈可以在 O(n)时间内完成这个计算；
3. 维护一个递增的单调栈，当遇到较小元素时，计算前面较大元素能形成的矩形面积。

最优 JavaScript 实现

function solution(n, array) {
    let maxArea = 0;
    const stack = [];
    
    for (let i = 0; i <= n; i++) { const currentHeight = i === n ? 0 : array[i]; while (stack.length > 0 && currentHeight < array[stack[stack.length - 1]]) {
            const height = array[stack.pop()];
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        
        stack.push(i);
    }
    
    return maxArea;
}

function main() {
    console.log(solution(5, [1, 2, 3, 4, 5]) === 9);  // true
    console.log(solution(6, [5, 4, 3, 2, 1, 6]) === 9);  // true
    console.log(solution(4, [4, 4, 4, 4]) === 16);  // true
}

main();

代码解释

1. 初始化maxArea为 0，用来记录最大面积
2. 使用一个栈来维护递增的高度索引
3. 遍历数组，并在最后添加一个高度 0 来处理栈中剩余元素
4. 当遇到比栈顶元素小的值时，弹出栈顶元素并计算面积：
   • 高度是弹出元素的高度
   • 宽度是当前索引与新的栈顶索引之间的差减 1（或当前索引，如果栈为空）
5. 更新最大面积
6. 最后返回计算得到的最大面积

这个算法的时间复杂度是 O(n)，因为每个元素最多入栈和出栈一次，空间复杂度也是 O(n)用于存储栈。

以上关于16. 最大矩形面积问题的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。