代码编织梦想

https://leetcode.cn/problems/0ynMMM/

题目要求

给定非负整数数组 heights ,数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

方法:双指针

  • 用两个双指针数组来记录每个柱子左右两边的第一个小于的柱子的坐标
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] minLeftIndex = new int[n];
        int[] minRightIndex = new int[n];

        minLeftIndex[0] = -1;// 注意这里初始化,防止下面while死循环
        for (int i = 1; i < n; i++) {
            int t = i - 1;
            while (t >= 0 && heights[t] >= heights[i]) {
                t = minLeftIndex[t];
            }
            minLeftIndex[i] = t;
        }
        minRightIndex[n - 1] = n;// 注意这里初始化,防止下面while死循环
        for (int i = n - 2; i >= 0; i--) {
            int t = i + 1;
            while (t < n && heights[t] >= heights[i]) {
                t = minRightIndex[t];
            }
            minRightIndex[i] = t;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            res = Math.max(res, sum);
        }
        return res;
    }

方法:单调栈

  • 实际上也是借助单调栈来找出左右的边界,然后遍历每个柱子的左右边界进行比较
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];// 记录左边界
        int[] right = new int[n];// 记录右边界

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[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();
            }
            right[i] = (stack.isEmpty() ? n : stack.peek());
            stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41830037/article/details/129817597

stack_dazhu233的博客-爱代码爱编程

Stack public class Stack<E> extends Vector<E> Stack是Vector的子类,是一个标准的先进后出的栈。 Stack有几个自己特有的方法。 Modifier and TypeMethod and Descriptionbooleanempty() Tests

np.stack()函数详解-爱代码爱编程

本文分了两部分,第一部分讲讲axis参数的理解,第二部分从np.stack函数的应用来反向理解该函数究竟干了些什么。 1.np.stack()中axis参数的深入理解 看了一下大家关于np.stack()的理解,我感觉自己还是一知半解,有点蒙。自己又想把这个函数搞明白 ,于是花了一点时间终于对这个函数有了自己的理解,决定把自己的想法写下来与大家分享,希

线性数据结构之栈(stack)_lingering fear的博客-爱代码爱编程

一.栈(Stack) 栈是一种用于存储数据的简单数据结构(与链表类似) , 栈的关键就是入栈的次序 , 比如我们在交作业的时候 , 最先交的永远都在最后面 , 而老师检查的时候是从最上面开始拿 , 所以第一个交的作业老师最