单调栈

想找 "从当前元素向某一方向的第一个 (大于 / 小于) 自己的元素"，就要靠单调栈来维护单调性，对应的是 (递减 / 递增)。

例题

有N个人，顺次排列，他们的身高分别为H[i]，每个人向自己后方看，他能看到的人是在他后面离他最近的且比他高的人。请依次输出每个人能看到的人的编号Next[i]，如果他后面不存在比他高的人，则输出-1。

这一题用的是递减栈，当一个元素不满足栈里面的单调性的时候，这个元素就把比他小的元素都pop出去，因此每个人就都知道了第一个比自己高的元素。

public class HigherPerson {
    public static int[] getHeight(int[] heights) {
        int n = heights.length;
        int[] result = new int[n];

        // stack store index
        LinkedList<Integer> stack = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            int value = heights[i];

            // error-prone: heights[stack.peek()]
            while(!stack.isEmpty() && heights[stack.peek()] < value) {
                int index = stack.pop();
                result[index] = i;
            }
            stack.push(i);
        }

        // can find higher person get -1
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        return result;

    }
}

Largest Rectangle in Histogram

顺着上一题的思路，这题比较暴力的解法可以分为三步：

• 从左向右扫，寻找对于每个元素，往右能看到的最远距离；
• 从右向左扫，寻找对于每个元素，往左能看到的远距离；
• 把两个 arr[] 的结果综合起来，就是从每个位置出发能构造的最大 rectangle.

虽然是O(n) ，但是有 three-pass。

更好的解法是，我们需要知道的是从当前点出发，找到左边第一个小于它的点的index,右边第一个小于它的点的index，高度是自己的高度，长度就是 rightIndex - leftIndex - 1 所以我们可以通过维护一个递增栈来实现，左边第一个小于它的index就是这个点在栈内左边的那个点，右边第一个小于它的点就是把它pop出去的那个点。这样通过one-pass就可以得到答案了。

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) {
            return 0;
        }

        // store index
        LinkedList<Integer> stack = new LinkedList<>();

        int maxArea = 0;

        // ascending stack
        for(int i = 0; i <= heights.length; i++) {
            int curValue = i == heights.length ? -1 : heights[i];
            while(!stack.isEmpty() && curValue <= heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;

                maxArea = Math.max(maxArea, h * w);
            }
            // otherwise, keep the monotone
            stack.push(i);
        }

        return maxArea;

    }
}