文章目录

• 1. 题目
• 2. 思路
• • (1) 单调栈
• 3. 代码

1. 题目

2. 思路

(1) 单调栈

• left[i]表示下标i左边第一个高度小于i的下标，right[i]表示下标i右边第一个高度小于i的下标。
• 利用单调栈高度小于当前下标的下标，则栈顶元素为左边或右边第一个小于当前下标的下标。

3. 代码

import java.util.Deque;
import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                left[i] = -1;
            } else {
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        stack = new LinkedList<>();
        int[] right = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                right[i] = n;
            } else {
                right[i] = stack.peek();
            }
            stack.push(i);
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
}