package LeetCode.stackpart03; /** * 84. 柱状图中最大的矩形 * */ public class LargestRectangleHistogram_84 { public int largestRectangleArea(int[] heights) { int length = heights.length; int[] minLeftIndex = new int [length]; int[] minRightIndex = new int [length]; // 记录左边第一个小于该柱子的下标 minLeftIndex[0] = -1 ; for (int i = 1; i < length; i++) { int t = i - 1; // 这里不是用if，而是不断向右寻找的过程 while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t]; minLeftIndex[i] = t; } // 记录每个柱子右边第一个小于该柱子的下标 minRightIndex[length - 1] = length; for (int i = length - 2; i >= 0; i--) { int t = i + 1; while(t < length && heights[t] >= heights[i]) t = minRightIndex[t]; minRightIndex[i] = t; } // 求和 int result = 0; for (int i = 0; i < length; i++) { int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1); result = Math.max(sum, result); } return result; } }