CSP 201312-3 最大的矩形 Java

96 阅读 0 评论 64 点赞

我是靠谱客的博主苗条鞋垫，这篇文章主要介绍CSP 201312-3 最大的矩形 Java，现在分享给大家，希望可以做个参考。

最大的矩形

单调栈，和力扣上的一个题目一样，可以参考下面的题解，有着更为详细的步骤：
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        int n = input.nextInt();
        //创建了两个哨兵，避免空值的判断
        int[] heights = new int[n + 2];
        for (int i = 1; i < heights.length - 1; i++) {
            heights[i] = input.nextInt();
        }
        
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        int res = 0;
        for (int i = 1; i < heights.length; i++) {
            while (heights[stack.peek()] > heights[i]) {
                int h = heights[stack.pop()];
                int w = i - stack.peek() - 1;
                res = Math.max(res, h * w);
            }
            stack.push(i);
        }
        
        System.out.println(res);
        
        input.close();
    }
}