1 题目

image.png

2 Java

class Solution {
    public int largestRectangleArea(int[] heights) {

        // 维护的是一个单调递增栈
        Stack<Integer> stack = new Stack<>();

        int num = heights.length;

        int[] left = new int[num];
        int[] right = new int[num];

        if(num == 0)
            return 0;

        left[0] = -1;
        right[num - 1] = num;

        for (int i = 0; i < num; i++) {
            while (!stack.empty() && heights[i] < heights[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                stack.push(i);
                left[i] = -1;
                continue;
            } else {
                if (heights[i] == heights[stack.peek()]) {
                    left[i] = left[stack.peek()];
                    stack.pop();
                    stack.push(i);
                } else {
                    left[i] = stack.peek();
                    stack.push(i);
                }
            }
        }

        stack = new Stack<Integer>();
        for (int i = num - 1; i >= 0; i--) {

            while (!stack.empty() && heights[i] < heights[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                right[i] = num;
                stack.push(i);
                continue;
            } else {
                if (heights[i] == heights[stack.peek()]) {
                    right[i] = right[stack.peek()];
                    stack.pop();
                    stack.push(i);
                } else {
                    right[i] = stack.peek();
                    stack.push(i);
                }
            }
        }


        int ans = Integer.MIN_VALUE;
        int curr;
        for (int i = 0; i < num; i++) {
            curr = (right[i] - left[i] - 1) * heights[i];
            ans = Math.max(ans, curr);
        }

        System.out.println(Arrays.toString(left));


        return ans;
    }
}

3 关键点

快速的写出单调栈这个工具的代码实现
单调栈维护的就是比当前位置小的第一个位置

  for (int i = num - 1; i >= 0; i--) {

            // 这里只要等于就pop
            while (!stack.empty() && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                right[i] = num;
            } else {
                right[i] = stack.peek();
            }
            stack.push(i);
        }