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

雨点打透心脏的1/2处 2022-10-01 07:56 130阅读 0赞

[Poj 2559 Largest Rectangle in a Histogram][]

[LeetCode 84 柱状图中最大的矩形][LeetCode 84][hdu 1506 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));
            }
        }
    }
    复制代码

转载于:https://juejin.im/post/5cba9509e51d456e7e297be5

[Poj 2559 Largest Rectangle in a Histogram]: https://link.juejin.im?target=http%3A%2F%2Fpoj.org%2Fproblem%3Fid%3D2559
[LeetCode 84]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Flargest-rectangle-in-histogram%2Fdescription%2F
[hdu 1506 Largest Rectangle in a Histogram]: https://link.juejin.im?target=http%3A%2F%2Facm.hdu.edu.cn%2Fshowproblem.php%3Fpid%3D1506