MENU

LeetCode84.柱状图中最大的矩形

August 13, 2018 • Read: 1143 • 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;
    }
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment