一道leetcode困难题的两种解法

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

这道题的关键在于找到每个柱子左边和右边第一个小于它的高度的柱子，这样的话可以使用单调栈来实现，代码如下：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

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

但是单调栈没有下面双指针的方法快：

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 双指针：对每个height[i]找左边第一个和右边第一个小于它的柱子下标，两个下表之间就是height[i]为高的的最大矩形的宽
        int len = heights.length;
        int[] minLeft = new int[len];
        int[] minRight = new int[len];
        minLeft[0] = -1;
        for (int i = 1; i < len; i++) {
            int j = i - 1;
            while (j >= 0 && heights[j] >= heights[i])
                j = minLeft[j];// 双指针的优化之处在于此，记忆化的思想记录左边的minLeft值避免重复搜索
            minLeft[i] = j;
        }
        minRight[len - 1] = len;
        for (int i = len - 2; i >= 0; i--) {
            int j = i + 1;
            while (j < len && heights[j] >= heights[i])
                j = minRight[j];// 双指针的优化之处
            minRight[i] = j;
        }
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum = Math.max(sum, heights[i] * (minRight[i] - minLeft[i] - 1));
        }
        return sum;

    }
}

双指针和单调栈的方法都利用单调性来使用已经求出的结果简化求值过程，但数组索引毕竟还是比入栈出栈来的快。