class Solution {
    //面积，（索引的差 + 1）*（高度的最小值）
    // 单调栈
    // 对于index位置的最大矩形的款是到左右两边第一次出现比heights[index]小的位置， 
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;  
		Deque<Integer> stack = new LinkedList<>();  
		int maxArea = 0;  
		
		for (int i = 0; i < heights.length; i++) {  
			// 当前柱子比栈顶小，说明找到了右边界  
			while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {  
				int top = stack.pop();  
				// 计算宽度  
				int maxWidth = stack.isEmpty() ? i : i - stack.peek() - 1;    
				maxArea = Math.max(maxWidth * heights[top], maxArea);  
			}  
			stack.push(i);  
		}  
		  
		// 处理右边没有更小柱子的情况  
		while (!stack.isEmpty()) {  
			int top = stack.pop();  
			int maxWidth = stack.isEmpty() ? n : n - stack.peek() - 1;  
			maxArea = Math.max(maxWidth * heights[top], maxArea);  
		}  
		  
		return maxArea;
    }
}