MENU

LeetCode84.柱状图中最大的矩形

August 13, 2018 • Read: 5242 • LeetCode阅读设置

题目链接:LeetCode84

题解

单调栈板子题,创建一个单调递增栈(栈底到栈顶是递增的),栈内存放的数组下标,遍历数组,将下标存进栈内,以样例来说

首先栈空,0直接进栈;然后因为nums[stack.peek()] > nums[1],所以0出栈了,同时记录以num[0]为高的矩形的面积,当前遍历到的数组下标为i,此时i是1,k等于0出站后,栈顶元素的下标,k= stack.isEmpty() ? -1 : stack.peek(),最终,底的长度就是i-k-1。

如果数组已经遍历到结束了,栈内还有值,就需要将他们依次弹出,此时的i=nums.length(),k=stack.isEmpty() ? -1 : stack.peek()。

整个流程用一个maxArea变量维护,找到最大值即可

代码
class Solution {
    public static int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0)
            return 0;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0;i < heights.length;i++) {
            while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                int curArea = (i - k - 1) * heights[j];
                maxArea = Math.max(maxArea,curArea);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) {
            int i = heights.length;
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (i - k - 1) * heights[j];
            maxArea = Math.max(maxArea,curArea);
        }
        return maxArea;
    }
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. 啊实打实的 啊实打实的

    for (int i = 0; i < n; i++) {//递增栈,遇到等于减少计算面积

    while (!stack.isEmpty() && num[i] < num[stack.peek()]){ int k = stack.peek(); int countBreadth = i - k; int newHeight = num[stack.pop()]; int countArea = newHeight * countBreadth; maxArea = Math.max(maxArea,countArea); } stack.push(i); } while(!stack.isEmpty()) { int k = stack.peek(); int countBreadth = n - k; int newHeight = num[stack.pop()]; int countArea = newHeight * countBreadth; maxArea = Math.max(maxArea,countArea); } return maxArea;
    1. 啊实打实的 啊实打实的

      @啊实打实的//递增栈,遇到等于减少计算面积会出bug,条件应改为
      !stack.isEmpty() && num[i] < num[stack.peek()]