LeetCode 84 & Poj 2559 & hdu 1506 求柱状图中最大的矩形

Poj 2559 Largest Rectangle in a Histogram

起初这题想了半天,然后瞄到一眼leetcode边上相关话题是"栈"....于是就想到用栈了.(尴尬) 这题若是从两个方向上分别来一次循环也是可以的(单调性),用了栈可以将两次循环合并(相当于剪枝). 用栈起初是没问题,但是我遇到了如 2,1,2 的情况时我就卡主了(当时我没有想到把出栈的数据改值重新入栈).然后参考了下网上其他人的思路才发现还能再压回去.

流程图 (从CSDN转来的流程图代码,掘金没有流程图生成功能...附上图片):

flowchat
st=>start: i=0
e=>end: 结束
putIn=>operation: i直接入栈
putOut=>operation: 出栈,具体操作见代码
iPlus=>operation: i++
ifEmpty=>condition: 是否空栈
ifSmaller=>condition: h[i]小于栈顶元素?
iEnd=>condition: i>length?

st->ifEmpty
ifEmpty(yes)->putIn
ifEmpty(no)->ifSmaller
putIn->iPlus
ifSmaller(yes)->putOut
ifSmaller(no)->putIn
putOut->iPlus
iPlus->iEnd
iEnd(yes)->e
iEnd(no)->ifEmpty
复制代码

JAVA代码 (LeetCode版本)

/**
     * 遍历数组
     * 1.栈为空则入栈
     * 2.若h[i]>=栈顶元素,入栈
     * 3.若h[i]<栈顶元素,则开始出栈计算面积,并将最后出栈的h[x]值改为h[i]再重新入栈
     *
     * @param heights 数组,本例会创建个新数组,在数组最后一个位置补个高度为0的图
     * @return 最大面积值
     */
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        Stack<Integer> s = new Stack<>();
        int[] h = new int[heights.length + 1];
        for (int i = 0; i < h.length; i++) {
            h[i] = i == heights.length ? 0 : heights[i];
            if (s.empty()) {
                //空栈直接入栈
                s.push(i);
                continue;
            }
            if (h[i] < h[s.peek()]) {
                //遇到小于栈顶的值,开始出栈,查找最大面积
                int top = 0;
                while (!s.empty() && h[s.peek()] > h[i]) {
                    top = s.pop();
                    max = Math.max((i - top) * h[top], max);
                }
                //将最后出栈的高度改为h[i]重新入栈
                h[top] = h[i];
                s.push(top);
                s.push(i);
            } else {
                s.push(i);
            }
        }
        return max;
    }
复制代码

Poj & hdu 版本 ps: poj&hdu的数据量要大一点,得使用long.

import java.util.Scanner;
import java.util.Stack;

public class Main {

    /**
     * 遍历数组
     * 1.栈为空则入栈
     * 2.若h[i]>=栈顶元素,入栈
     * 3.若h[i]<栈顶元素,则开始出栈计算面积,并将最后出栈的h[x]值改为h[i]再重新入栈
     *
     * @param heights 数组,本例会创建个新数组,在数组最后一个位置补个高度为0的图
     * @return 最大面积值
     */
    public long largestRectangleArea(int[] heights) {
        long max = 0;
        Stack<Integer> s = new Stack<Integer>();
        int[] h = new int[heights.length + 1];
        for (int i = 0; i < h.length; i++) {
            h[i] = i == heights.length ? 0 : heights[i];
            if (s.empty()) {
                //空栈直接入栈
                s.push(i);
                continue;
            }
            if (h[i] < h[s.peek()]) {
                //遇到小于栈顶的值,开始出栈,查找最大面积
                int top = 0;
                while (!s.empty() && h[s.peek()] > h[i]) {
                    top = s.pop();
                    max = Math.max((i - top) * (long)h[top], max);
                }
                //将最后出栈的高度改为h[i]重新入栈
                h[top] = h[i];
                s.push(top);
                s.push(i);
            } else {
                s.push(i);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Main n84 = new Main();
//        System.out.println(n84.largestRectangleArea(new int[]{1,2,3,2,1,5,6,2,3,2,2}));
        // oj summit version
        Scanner scan = new Scanner(System.in);
        int n;
        while ((n = scan.nextInt()) != 0) {
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = scan.nextInt();
            }
            System.out.println(n84.largestRectangleArea(array));
        }
    }
}
复制代码