---
tags: Cmoney_Java題目
---
Java_Cmoney_ft9106_計算長條圖中的正方形面積
===
重要資料
1. [Leetcode](https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28900/Short-and-Clean-O(n)-stack-based-JAVA-solution/213800)
2. [[演算法] Largest Rectangle in Histogram 筆記](https://medium.com/hoskiss-stand/largest-rectangle-b3a7473320c1)
3. [【Day 29】#84 - Largest Rectangle in Histogram](https://ithelp.ithome.com.tw/articles/10229343)


1.需要的 function
---
1.1 計算最大的長方形面積(暴力解)
---

public static int largestRectangle(int[] heights) {
        int maxArea = 0;
        int len = heights.length;
        for (int i = 0; i < len; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < len; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

1.1 計算最大的長方形面積(使用 Stack)
---
1. Stack 特性 : 後進先出
2. 迴圈
1. `i <= len`，使用哨兵技巧
2. `int h = (i == len ? 0 : heights[i]);`，長條圖之外再加一個高度為0的長條圖
3. 如果 Stack 是空 || h 高於 Stack 裡最上層(最大)的高度，就把 h push 進去，然後 i++，前往下一個長條圖高度
1. ==條件不可顛倒`(h > heights[s.peek()] || s.isEmpty() )`，因為如果 Stacj 是空的，`.peek()`不能執行==
2. ==比高度所以記得是`heights[s.peek()]`不是`s.peek()`==
3. ==`h > heights[s.peek()]` 和 `h >= heights[s.peek()]`都可以==
4. 否則結算面積
1. 高度 : pop 出最上層，`heights[s.pop()]`
2. 右邊邊界 : i - 1 ( i 為下降的長條圖 )
3. 左邊邊界 :
1. 如果 Stack 是空的，可以一直延伸到 0
2. 不是就 peek()+1， Stack 最上層的右邊一個
4. 寬度 : `rightBound - leftBound + 1`
5. 最大面積 : `Math.max(maxArea, currentHeight * width)`
5. 回傳最大面積

public static int largestRectangle(int[] heights) {
        int maxArea = 0;
        Stack<Integer> s = new Stack<>();
        int len = heights.length;
        for (int i = 0; i <= len; ) {
            int h = (i == len ? 0 : heights[i]);
            if (s.isEmpty() || h > heights[s.peek()]) {
                s.push(i);
                i++;
            } else {
                int currentHeight = heights[s.pop()];
                int rightBound = i - 1;
                int leftBound = s.isEmpty() ? 0 : s.peek() + 1;
                int width = rightBound - leftBound + 1;
                maxArea = Math.max(maxArea, currentHeight * width);
            }
        }
        return maxArea;
    }

2.全部程式
---

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


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
        }
        System.out.println(largestRectangle(numbers));

    }

    public static int largestRectangle(int[] heights) {
        int maxArea = 0;
        Stack<Integer> s = new Stack<>();
        int len = heights.length;
        for (int i = 0; i <= len; ) {
            int h = (i == len ? 0 : heights[i]);
            if (s.isEmpty() || h > heights[s.peek()]) {
                s.push(i);
                i++;
            } else {
                int currentHeight = heights[s.pop()];
                int rightBound = i - 1;
                int leftBound = s.isEmpty() ? 0 : s.peek() + 1;
                int width = rightBound - leftBound + 1;
                maxArea = Math.max(maxArea, currentHeight * width);
            }
        }
        return maxArea;
    }

}