84. Largest Rectangle in Histogram 发表于 2022-05-23 1234567891011121314151617181920212223242526class Solution { public int largestRectangleArea(int[] heights) { int[] heightsWithSentinel = new int[heights.length + 2]; // 右侧哨兵用于触发最后的计算,左侧哨兵用于简化左侧边界索引的获取,不用判断栈中元素是否为空 for (int i = 0; i < heights.length; i++) { heightsWithSentinel[i + 1] = heights[i]; } heights = heightsWithSentinel; int maxArea = 0; Stack<Integer> increaseStack = new Stack<>(); // 非严格递增栈,栈中存储的索引 for (int i = 0; i < heights.length; i++) { while (!increaseStack.isEmpty() && heights[i] < heights[increaseStack.peek()]) { int height = heights[increaseStack.pop()]; int rightIndex = i; // exclusive int leftIndex = increaseStack.peek(); // exclusive, 注意左侧边界是栈顶索引,而不是 tallIndex,可以用 [2, 1, 2] 加深记忆 int width = rightIndex - leftIndex - 1; maxArea = Math.max(maxArea, height * width); } increaseStack.push(i); // 不要忘记将当前柱子索引入栈 } return maxArea; }} Reference84. Largest Rectangle in Histogram