介紹：單調(diào)棧是一種按照元素單調(diào)遞增或遞減的順序排列的數(shù)據(jù)結(jié)構(gòu)。

相關(guān)題目

1. 柱狀圖中最大的矩形

image.png

第一種：暴力解法：

第二種：單調(diào)棧：

    public int largestRectangleArea(int[] heights) {
        if (heights == null) {
            return 0;
        }
        
        int size = heights.length;
        int[] input = new int[size + 2];
        input[0] = 0;
        input[size + 1] = 0;
        
        // 記得初始化
        for(int index = 1; index < size + 1; index++) {
            input[index] = heights[index - 1];
        }
        
        int[] result = new int[size + 2];
        
        Stack<Integer> stack = new Stack<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < size + 2; i++) {
            // 重點：如果新的元素比棧頂top元素小，則需說明當(dāng)前遞增的規(guī)律被打破了，為了使新的元素入棧，需要將破壞規(guī)矩的元素出棧，并計算結(jié)果
            while(!stack.isEmpty() && (input[stack.peek()] > input[i])) {
                int top = stack.pop();
                int left = stack.peek();
                result[top] = (i - left - 1) * input[top];
                max = Math.max(result[top], max);
            }
            // 入棧的是索引，而不是元素內(nèi)容
            stack.push(i);
        }
        return max;
    }