一、LeetCode84. 柱狀圖中最大的矩形

題目鏈接：84. 柱狀圖中最大的矩形

題目描述：

給定?n?個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例 1:

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區域，面積為 10

示例 2：

輸入： heights = [2,4]
輸出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

算法分析：

直接上代碼：

class Solution {int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>();// 數組擴容，在頭和尾各加入一個元素int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int index = 0; index < heights.length; index++){newHeights[index + 1] = heights[index];}heights = newHeights;st.push(0);int result = 0;// 第一個元素已經入棧，從下標1開始for (int i = 1; i < heights.length; i++) {// 注意heights[i] 是和heights[st.top()] 比較 ，st.top()是下標if (heights[i] > heights[st.peek()]) {st.push(i);} else if (heights[i] == heights[st.peek()]) {st.pop(); // 這個可以加，可以不加，效果一樣，思路不同st.push(i);} else {while (heights[i] < heights[st.peek()]) { // 注意是whileint mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];result = Math.max(result, w * h);}st.push(i);}}return result;}
}