问题描述

求直方图中最大的矩阵面积。

举个例子：

解法1

Thanks @tt2767{:target=”_blank”}

先来看下示意图：

梳理下思路：

首先，遍历整个数组，对于每个元素都需要求两个东西：

第一，在它之前，比它小的第一个元素的索引。

第二，在它之后，比它小的第一个元素的索引。

并依次将其存储左右两个数组中。

然后，明确两点：

第一点，栈中存的是索引，便于计算宽度，以及防止重复。

第二点，栈具有单调递增的特点。

来看下实现：

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

         int n = heights.length;
        // Store indices.
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        int[] left  = buildLeftBound(heights, stack);
        int[] right = buildRightBound(heights, stack);

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

    private int[] buildLeftBound(int[] h, ArrayDeque<Integer> stack){
        int n = h.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++){
            int cur = h[i];
            while (!stack.isEmpty() && h[stack.peek()] >= cur){
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        return ans;
    }

    private int[] buildRightBound(int[] h, ArrayDeque<Integer> stack){
        stack.clear();
        int n = h.length;
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; i--){
            int cur = h[i];
            while (!stack.isEmpty() && h[stack.peek()] >= cur){
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        return ans;
    }
}

Enjoy it !