【重点!!!】【单调栈】84.柱状图中最大矩形

2023-12-26 06:47:57

题目

法1:单调栈[原版]

O(N)+O(N)
必须掌握算法!!!

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length, res = 0;
        int[] leftMin = new int[n], rightMin = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            leftMin[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            rightMin[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        for (int i = 0; i < n; ++i) {
            res = Math.max(res, (rightMin[i] - leftMin[i] - 1) * heights[i]);
        }

        return res;
    }
}

法2:单调栈[优化版]

O(N)+O(N)
参考答案
在这里插入图片描述

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length, res = 0;
        int[] leftMin = new int[n], rightMin = new int[n];
        Arrays.fill(rightMin, n); // 一定注意这次需要初始化!!!
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                rightMin[stack.peek()] = i;
                stack.pop();
            }
            leftMin[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        for (int i = 0; i < n; ++i) {
            res = Math.max(res, (rightMin[i] - leftMin[i] - 1) * heights[i]);
        }

        return res;
    }
}

文章来源:https://blog.csdn.net/Allenlzcoder/article/details/135189841
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。