当前位置：首页 > article >正文

算法练习题14——leetcode84柱形图中最大的矩形（单调栈）

article 2024/11/17 3:24:25

题目描述：

解题思路：

要解决这个问题，我们需要找到每个柱子可以扩展的最大左右边界，然后计算以每个柱子为高度的最大矩形面积。

具体步骤如下：

计算每个柱子左侧最近的比当前柱子矮的位置：
- 使用一个单调栈（栈中保存元素索引）从左到右遍历柱子，确保栈中元素始终保持递增（从栈底到栈顶）。
- 如果当前柱子的高度小于栈顶柱子的高度，则不断弹出栈顶元素，直到找到一个高度小于当前柱子的元素为止。
- 这样可以确定每个柱子左边第一个比它矮的位置。
计算每个柱子右侧最近的比当前柱子矮的位置：
- 使用类似的单调栈方法，从右到左遍历柱子，确保栈中元素始终保持递增。
- 同样地，可以确定每个柱子右边第一个比它矮的位置。
计算最大矩形面积：
- 计算每个柱子可以扩展的宽度，使用公式 (right[i] - left[i] - 1) * heights[i] 来计算以该柱子为高度的矩形面积。
- 遍历所有柱子，找到最大面积。

代码示例：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n]; // 用于存储每个柱子的左边界
        int[] right = new int[n]; // 用于存储每个柱子的右边界
        Stack<Integer> stack = new Stack<>(); // 用于计算左右边界的单调栈

        // 从左到右遍历柱子，计算每个柱子左边第一个比它矮的位置
        for (int i = 0; i < n; i++) {
            // 如果栈不为空且栈顶柱子的高度大于等于当前柱子的高度，弹出栈顶元素
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            // 如果栈为空，说明当前柱子左侧没有比它矮的柱子
            if (stack.isEmpty()) {
                left[i] = -1; // 左边界为-1
            } else {
                left[i] = stack.peek(); // 栈顶元素即为左边第一个比当前柱子矮的位置
            }
            // 将当前柱子的索引压入栈中
            stack.push(i);
        }

        stack.clear(); // 清空栈，用于计算右边界

        // 从右到左遍历柱子，计算每个柱子右边第一个比它矮的位置
        for (int i = n - 1; i >= 0; --i) {
            // 如果栈不为空且栈顶柱子的高度大于等于当前柱子的高度，弹出栈顶元素
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            // 如果栈为空，说明当前柱子右侧没有比它矮的柱子
            if (stack.isEmpty()) {
                right[i] = n; // 右边界为n
            } else {
                right[i] = stack.peek(); // 栈顶元素即为右边第一个比当前柱子矮的位置
            }
            // 将当前柱子的索引压入栈中
            stack.push(i);
        }

        int ans = 0; // 用于存储最大矩形面积
        // 遍历每个柱子，计算以该柱子为高度的最大矩形面积
        for (int i = 0; i < n; i++) {
            // 以heights[i]为高度的矩形面积计算公式为：(right[i] - left[i] - 1) * heights[i]
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans; // 返回最大矩形面积
    }
}

详细解题步骤：

初始化数组和栈：
- left[i] 存储柱子 i 左侧第一个比其矮的柱子的索引，如果不存在，设置为 -1。
- right[i] 存储柱子 i 右侧第一个比其矮的柱子的索引，如果不存在，设置为 n。
- 使用 Stack 存储柱子的索引，用于计算左右边界。
计算左边界：
- 遍历所有柱子：
  - 如果当前柱子的高度小于栈顶柱子的高度，弹出栈顶元素，直到找到一个高度小于当前柱子的元素。
  - 如果栈为空，说明当前柱子左侧没有比它矮的柱子，设置 left[i] = -1。
  - 否则，设置 left[i] = stack.peek()，即栈顶元素是左边第一个比当前柱子矮的位置。
- 将当前柱子的索引压入栈中。
计算右边界：
- 从右到左遍历所有柱子：
  - 使用类似的方法计算每个柱子右边第一个比它矮的位置。
计算最大矩形面积：
- 遍历所有柱子，以每个柱子作为最矮柱子，计算矩形的最大面积。
- 使用公式 (right[i] - left[i] - 1) * heights[i] 来计算每个柱子的最大矩形面积。